Kth Smallest Element in a Sorted Matrix

Share

Given an n x n matrix where each row and column is sorted in ascending order, find the kth smallest element in the matrix.

Example 1
Input: matrix=[[1,5,9],[10,11,13],[12,13,15]], k=8 → Output: 13
Example 2
Input: matrix=[[-5]], k=1 → Output: -5

Solution Approach

Binary search on the answer value (not index). Count elements <= mid. The kth smallest is the smallest value v such that count(v) >= k.

  • lo=matrix[0][0], hi=matrix[n-1][n-1].
  • For mid, count elements <= mid by traversing rows from bottom-left.
  • If count >= k: hi=mid. Else lo=mid+1.
  • lo converges to the kth smallest element.
Java
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int lo = matrix[0][0], hi = matrix[n-1][n-1];
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0, j = n - 1;
            for (int i = 0; i < n; i++) {
                while (j >= 0 && matrix[i][j] > mid) j--;
                count += j + 1;
            }
            if (count >= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}
  • Time Complexity: O(N log(max-min))
  • Space Complexity: O(1)