Kth Smallest Element in a Sorted Matrix

Kth Smallest Element in a Sorted Matrix

1. What is this problem about?

The Kth Smallest Element in a Sorted Matrix interview question asks you to find the $k^{th}$ smallest value in an $n imes n$ matrix where each row and each column is sorted in ascending order. Note that it is the $k^{th}$ smallest in the overall sorted order, not the $k^{th}$ distinct element.

2. Why is this asked in interviews?

This is a standard question at Google, Apple, and Salesforce. It tests your ability to choose between two powerful optimization strategies: Heaps and Binary Search on Value. it evaluations how you handle multi-dimensional sorted data and if you can find a solution better than $O(N^2 \log N^2)$.

3. Algorithmic pattern used

There are two main patterns:

1. Min-Heap ($O(K \log N)$): Treat the matrix as $N$ sorted lists. Push the first element of each row into a Min-Heap. Pop the smallest element $k$ times, each time pushing the next element from the same row.
2. Binary Search on Range ($O(N \log (\max - \min))$): The answer is between the top-left and bottom-right elements. For a mid-value $X$, count how many elements in the matrix are $\leq X$ using a linear $O(N)$ scan from the bottom-left corner.

4. Example explanation

Matrix:

1  5  9
10 11 13
12 13 15

Find $k = 8$.

• Range is [1, 15]. Try mid = 8.
• Count elements $\leq 8$: Only {1, 5}. Count = 2.
• Since $2 < 8$, we need a larger value. Try mid = 12.
• Count elements $\leq 12$: {1, 5, 9, 10, 11, 12}. Count = 5.
• ... Continue until the binary search converges on the $8^{th}$ element.

5. Common mistakes candidates make

• Sorting the whole matrix: $O(N^2 \log N^2)$ is too slow for large matrices.
• Wrong binary search: Trying to binary search on the index instead of the value range.
• Inefficient counting: Using $O(N^2)$ to count elements $\leq X$ inside the binary search, which results in $O(N^2 \log ( ext{Range}))$.

6. Interview preparation tip

Master the O(N) Matrix Count trick. You can count how many elements are $\leq X$ in a row/column sorted matrix by starting at the bottom-left and moving only "Up" or "Right." This is a foundational Matrix interview pattern.