Problem

Kth Smallest Element in a Sorted Matrix

Description

  1. Binary search can’t be used directly, because elements in one column may be same.
  2. But We can convert the thought about binary search. Let’s define the most minimal value is matrix[0][0] and the maximum value is matrix[N - 1][N - 1]. Then left & right can be updated by the number of elements that are smaller than mid.

Code

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int N = matrix.length, l = matrix[0][0], r = matrix[N - 1][N - 1];
        while(l <= r){
            int mid = (r - l) / 2 + l;
            int cnt = 0;
            for(int i = 0; i < N; i ++){
                for(int j = 0; j < N; j ++){
                    if(matrix[i][j] > mid) break;
                    cnt ++;
                }
            }
            if(cnt >= k){
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        return l;
    }
}