378. Kth Smallest Element in a Sorted Matrix - Detailed Explanation

Problem Statement

You are given an n x n matrix where each row and each column is sorted in ascending order. Your task is to find the kth smallest element in the matrix, where kth smallest means the kth element in the sorted order of all elements (note that the kth smallest is not necessarily the kth distinct element).

For example, consider the following matrix and k:

matrix = [
  [ 1,  5,  9],
  [10, 11, 13],
  [12, 13, 15]
]
k = 8

The sorted order of the elements in the matrix is:

[1, 5, 9, 10, 11, 12, 13, 13, 15]

The 8th smallest element is 13.

Approaches

There are two common and efficient approaches to solve this problem:

Approach 1: Using a Min-Heap (Priority Queue)

Idea

Because each row (and column) is sorted, you can use a min-heap to efficiently merge the rows. The idea is to:

1. Initialize the heap:
   • Push the first element of each row into a min-heap along with its row and column indices.
2. Extract and Process Elements:
   • Pop the smallest element from the heap. This is the current smallest element.
   • If the element has a next element in its row, push that next element into the heap.
   • Repeat this process k times. The kth element popped from the heap is the kth smallest element in the matrix.

Complexity

• Time Complexity:
  O(k log n) because we perform k extract-min operations from a heap that contains at most n elements.

• Space Complexity:
  O(n) for the heap.

Pitfall

• Make sure to only push the next element in the same row to avoid duplicate processing and to maintain the sorted order by rows.

Approach 2: Binary Search on Value Range

Idea

Since the matrix is sorted both row-wise and column-wise, you can perform a binary search on the value range (not the index). The steps are:

1. Define the Search Range:
   • The smallest element is matrix[0][0] and the largest element is matrix[n-1][n-1].
2. Binary Search Process:

   • Pick a middle value (mid) in the range.

   • Count the number of elements in the matrix that are less than or equal to mid.
     Because each row is sorted, you can count this in O(n) per row.

   • If the count is less than k, it means the kth smallest element is larger than mid; otherwise, it is less than or equal to mid.

   • Adjust the search range accordingly until you pinpoint the kth smallest element.

Counting Elements

• To count how many numbers are ≤ mid, start from the bottom-left or top-right of the matrix and move through the matrix in O(n) time.

Complexity

• Time Complexity:
  O(n log(max - min)) where max and min are the largest and smallest elements in the matrix.

• Space Complexity:
  O(1) extra space.

Detailed Walkthrough for Binary Search Approach

1. Initialize the Search Range:
   Let lo = matrix[0][0] and hi = matrix[n-1][n-1].

2. Binary Search Loop:

   • While lo < hi:

     • Compute mid = lo + (hi - lo) // 2.

     • Count the number of elements in the matrix that are ≤ mid.

     • If the count is less than k, set lo = mid + 1; else, set hi = mid.

3. Result:
   After the loop terminates, lo (or hi) will be the kth smallest element.

Python Code

Java Code

Edge Cases

• Single Element Matrix:
  If the matrix has only one element (n = 1), then that element is the answer regardless of k.

• k equals 1 or n²:
  When k is 1, the answer is matrix[0][0]; when k is n², the answer is matrix[n-1][n-1].

• Duplicate Values:
  The algorithm must correctly count duplicates. For instance, if there are multiple occurrences of the same number, each occurrence is counted toward the kth smallest.

Common Mistakes

1. Incorrect Heap Initialization:
   • Pushing too many or too few elements into the heap can result in either missing candidates or processing unnecessary elements.
2. Improper Counting in Binary Search:
   • When counting the elements ≤ mid, ensure that you efficiently use the sorted order of rows and columns. A naive approach could lead to an O(n²) count per mid value.
3. Off-by-One Errors:
   • In binary search, carefully manage the boundaries (lo and hi) to ensure that the kth smallest element is correctly identified.
4. Not Handling Duplicates:
   • Failing to count duplicates correctly might lead to an incorrect kth value.

Related LeetCode Problems

• Kth Largest Element in an Array (LeetCode 215)

• Merge k Sorted Lists (LeetCode 23)

• Search a 2D Matrix (LeetCode 74)