The O(n) Club: Kth Smallest in a Sorted Matrix: Aka Why Binary Search Beats Brute Force (and Caffeine)

The O(n) Club: Kth Smallest in a Sorted Matrix: Aka Why Binary Search Beats Brute Force (and Caffeine)

⚡ TL;DR

You want the kth smallest number in an n x n matrix with each row and column sorted—yes, like organized Tupperware. Most people flatten, sort, and pray, but binary search on the value range makes brute force look like dial-up. Example:

// Brute force: flatten, sort, pick kth
List<Integer> flat = new ArrayList<>();
for (int[] row : matrix) for (int val : row) flat.add(val);
Collections.sort(flat);
return flat.get(k - 1); // Time: O(n^2 log n)

🧠 How Devs Usually Mess This Up

Classic move: ignore the ‘not globally sorted’ warning, start zig-zagging diagonally, or fire up a min-heap like it’s a barbecue. Most rookie mistakes? Treating the matrix like it’s just one big sorted pancake—it’s not. Or, attempting merger logic usually reserved for three-day hackathons. And let’s not forget the people who do binary search on indices instead of values (spoiler: the algorithm weeps).

🔍 What’s Actually Going On

Think of your matrix as a city where each street (row) and avenue (column) is in order, but there’s no single skyscraper overseeing the whole city. We’re after the kth smallest building—could be hidden anywhere, not just down one block. The big trick? Binary search through all possible values (lowest to highest), not where they are, but what they are. To check if your ‘guess’ covers enough buildings, you efficiently count how many are below or at each guess, using the sorted nature of the roads to cut down detours like a pro GPS. Bonus: duplicates totally count. The answer might be ’42’, twice.

🛠️ PseudoCode

• Define low/high: int low = matrix[0][0], high = matrix[n-1][n-1];
• While low < high:
  • Midpoint: mid = (low + high) / 2
  • Count nums ≤ mid:
    • Start at bottom-left corner.
    • If matrix[row][col] ≤ mid, all above in that column are also ≤ mid: add row + 1 to count, move right.
    • If matrix[row][col] > mid, move up.
  • If count >= k: high = mid
  • If count < k: low = mid + 1
• Return low.