Binary Search - Kth Smallest Element in a Sorted Matrix

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

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

Input: matrix=[[-5]], k=1 → Output: -5

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.

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)