• LeetCode - 240

Brutal Force

Brutal force would take O(m*n) that go through all elements.

Binary Search

A better approach is to use binary search on each of the row or col. This takes O(MlogN).

Saddleback Search

Saddleback search takes the advantage of sorted row and col. We can start from the bottom left or top right elements. There are three cases:

1. target == current: we found it;
2. target < current: we have to move one column backward, because all the element after the current column is more than current.
3. target > current: we move one row forward, because element below is more than current. This approach takes O(m+n);

    public boolean searchMatrix(int[][] matrix, int target) {
      int sRow = 0;
      int sCol = matrix.length > 0 ? matrix[0].length-1 : -1;
           
      while(sRow < matrix.length && sCol >= 0) {
          if (matrix[sRow][sCol] > target) sCol--;
          else if (matrix[sRow][sCol] < target) sRow++;
          else return true;
      }
           
      return false;
       }
   

• LeetCode - 378

### Sort approach

A simple approach is to put all elements in a max priority queue (keep queue size to k), and then pop up the first element of the queue. This approach takes O(mnlogk). And it could be used to any matrix.

### Saddleback search

To take the advantage of sorted properties, we could use saddle back search with binary search method. The element should be between the first element and the last element, so we can do binary search in this range, and count the the ranking of this number by saddleback search.

    public int kthSmallest(int[][] matrix, int k) {
        
        int n = matrix.length;
        int left = matrix[0][0], right = matrix[n-1][n-1];
        int res = 0;
        while (left <= right) {
            int mid = left + (right - left)/2;
            int count = countLessThan(matrix, mid);
            if (count >= k) {
                res = mid;
                right = mid-1;
            } else {
                left = mid + 1;
            }            
        }
        return res;
    }
    
    private int countLessThan(int[][] matrix, int val) {
        //saddle back search to count the position of value.
        int count = 0;
        int i = 0, j = matrix.length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] > val) {
                j--;
            } else {
                i++;
                count += j+1;
            }
        }
        return count;
    }