BS on Answer — Kth Smallest Element in a Sorted Matrix

↗ LeetCode: Kth Smallest Element in a Sorted Matrix · Medium · pattern chapter →

Asked atMetaAmazonGoogleUberBloomberg

Given n×n matrix sorted row and column, return the k-th smallest element.

Example 1 — matrix=[[1,5,9],[10,11,13],[12,13,15]], k=8 → 13Example 2 — matrix=[[-5]], k=1 → -5Example 3 — matrix=[[1,2],[1,3]], k=2 → 1

Constraints — 1 ≤ n ≤ 300; 1 ≤ k ≤ n². Brute flatten-and-sort is O(n² log n²) = 300² · log(9·10⁴) ≈ 10⁶ ops. BS-on-answer is O(n · log(max-min)) ≈ 300 · 32 = 10⁴.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Flatten + sort

O(n² log n²).

Approach 2 — Min-heap of rows

Heap starts with each row's head. Pop-then-push-next k-1 times. O((n+k) log n).

Approach 3 — Binary search on value

Insight. countLE(v) = elements ≤ v. Monotonic in v. Binary search for the smallest v with countLE(v) ≥ k. countLE uses staircase walk from bottom-left: O(n).

int kthSmallest(int[][] m, int k) {
    int n = m.length;
    int lo = m[0][0], hi = m[n - 1][n - 1];
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int count = 0, r = n - 1, c = 0;
        while (r >= 0 && c < n) {
            if (m[r][c] <= mid) { count += r + 1; c++; }
            else                r--;
        }
        if (count < k) lo = mid + 1;
        else           hi = mid;
    }
    return lo;
}

Execution Trace

BS on value — matrix=[[1,5,9],[10,11,13],[12,13,15]], k=8

Step 1 / 52 lt 8 → lo=9

Complexity — Time O(n log(max-min)); Space O(1).

Try it yourself

Complexity summary

Approach	Time	Space
Flatten + sort	O(n² log n)	O(n²)
Heap of rows	O((n+k) log n)	O(n)
BS on value	O(n log(max-min))	O(1)

When to use which

• Sorted matrix kth → BS on value or min-heap merge.
• BS on value is cleaner for max n; heap wins for small n.
• Kth in unsorted → Quickselect or heap.

✨AI Study CompanionBeta

Related problems

• Find K-th Smallest Pair Distance
• Median of Two Sorted Arrays
• Search a 2D Matrix II — same staircase walk

Was this page helpful?