Kth Smallest Element in a Sorted Matrix

MediumK-Way Merge · Binary Search on Value🧩 K-Way Merge LeetCode #378 ↗Updated Oct 30, 2026

Problem

An n x n matrix has every row and every column sorted in non-decreasing order. Return the k-th smallest value in the whole matrix, counting duplicates (it is the k-th element of the sorted multiset, not the k-th distinct value). Aim for better than O(n²) memory.

Input[[1,5,9],[10,11,13],[12,13,15]], k=8Output13

Input[[-5]], k=1Output-5

1 ≤ n ≤ 300 · -10⁹ ≤ matrix[i][j] ≤ 10⁹ · 1 ≤ k ≤ n² · Follow-up: O(1) extra memory?

Try it yourself

Java

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Search the value range, not the indices. For any value x you can count entries ≤ x in O(n) by walking a staircase from the bottom-left corner; the answer is the smallest x with count ≥ k.

PatternK-Way Merge

Instinct Several sorted lists, rows or streams and you need the global order, the k-th smallest or a range: keep one cursor per list in a min-heap.

Memory hack Line up the heads, crown the smallest, then let its next-in-line step up.

Open the K-Way Merge guide →

Approaches

Brute ForceFlatten & Sort

Time O(n² log n)Space O(n²)

Ignore the sorted structure: copy all n² values into one array, sort it, and read index k-1.

Java

public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length, idx = 0;
    int[] all = new int[n * n];
    for (int[] row : matrix) {
        for (int v : row) all[idx++] = v;
    }
    Arrays.sort(all);
    return all[k - 1];
}

Trivial and correct, but wastes the sortedness and stores every cell.

BetterMin-Heap K-Way Merge

Time O(k log n)Space O(n)

Each row is a sorted list, so merge them like k sorted lists: seed a min-heap with the first cell of each row, then pop k times, pushing the popped cell's right neighbour. The k-th pop is the answer. Only min(n, k) rows can matter.

Java

public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;
    // {value, row, col}; Integer.compare avoids overflow of a[0] - b[0]
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    for (int r = 0; r < Math.min(n, k); r++) heap.offer(new int[]{matrix[r][0], r, 0});
    int[] cur = null;
    for (int i = 0; i < k; i++) {
        cur = heap.poll();
        int r = cur[1], c = cur[2];
        if (c + 1 < n) heap.offer(new int[]{matrix[r][c + 1], r, c + 1});
    }
    return cur[0];
}

Great for small k; degrades to O(n² log n) when k ≈ n².

OptimalBinary Search on Value + Staircase Count

Time O(n log(max−min))Space O(1)

Binary search x in [matrix[0][0], matrix[n-1][n-1]]. To count cells ≤ x, start bottom-left: if the cell is ≤ x, the whole column above it is too (add row+1, go right); else go up. The smallest x with count ≥ k always exists in the matrix.

Java

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 = (int) (((long) lo + hi) >> 1); // floor, no int overflow
        if (countLessEqual(matrix, mid) < k) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
private int countLessEqual(int[][] m, int x) {
    int n = m.length, row = n - 1, col = 0, count = 0;
    while (row >= 0 && col < n) {
        if (m[row][col] <= x) {
            count += row + 1; // the whole column up to row is <= x
            col++;
        } else {
            row--;
        }
    }
    return count;
}

Linear work per probe, ~32 probes, constant memory — answers the follow-up.

Pro tip

hi - lo can reach 2·10⁹, so compute mid in long; use floor (>> 1) so negatives still converge.

At a glance

Level	Approach	Time	Space
Brute Force	Flatten & Sort	`O(n² log n)`	`O(n²)`
Better	Min-Heap K-Way Merge	`O(k log n)`	`O(n)`
Optimal	Binary Search on Value + Staircase Count	`O(n log(max−min))`	`O(1)`

Common pitfalls

mid = lo + (hi - lo) / 2 overflows int when values span ±10⁹.
Returning the first mid whose count equals k — it may not be in the matrix.
Heap comparator a[0] - b[0] overflows on large negative/positive values.

Interview tips

Start with flatten-and-sort, then point out each row is a sorted list (k-way merge).
Explain why lo ends on a real matrix value (smallest x with count ≥ k).
Draw the staircase count — same walk as Search a 2D Matrix II (240).

Pattern

Binary search on the answer + monotone count → k-th smallest in sorted rows/columns or pair sums.

My notes saved in this browser