Idea 1 (binary search)

• Solved with O(1) memory complexity & O(n logn) time complexity, the binary search part takes O(logn), then in each search we perform countSmallerEqual() which takes O(n)
• Read the comments in the codes below to find out why the solution work

class Solution {
  public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;

    // the ans is within the left and right range (inclusive)
    int left = matrix[0][0];
    int right = matrix[n - 1][n - 1];

    // Since it is within the range, if there is only one value left in the
    // range, then it must be the answer!
    while (left < right) {
      int mid = left + (right - left) / 2;

      int count = countSmallerEqual(mid, matrix);

      if (count < k) { // value is bigger than mid
        left = mid + 1;
      } else { // value is mid or smaller
        right = mid;
      }
    }

    return left;
  }

  // Time O(n), instead of O(n^2) which goes through each cell
  public int countSmallerEqual(int midVal, int[][] matrix) {
    int n = matrix.length;

    int r = n - 1; // we check from the bottom
    int c = 0; // we start from first column

    int count = 0;

    while (r >= 0 && c < n) { // when r<0, it is out of the matrix
      if (matrix[r][c]
          <= midVal) { // midVal covers the entire column from the r and below
        count += (r + 1);
        c++; // go check the next column
      } else {
        r--; // the value in the same row is bigger, so 100% can be ignore
      }
    }

    return count;
  }
}

Idea 2 (priority queue)