What is the brute force approach and complexity for Kth Smallest Element in a Sorted Matrix?

Copy all n² values into one list, sort it, and read position k with time complexity O(N² log N) and space complexity O(N²).

What is the optimal approach and complexity for Kth Smallest Element in a Sorted Matrix?

Min-heap with one front cell per row; take k values out and push the cell to the right with optimal time complexity O(K log min(N, K)) and space complexity O(min(N, K)).

How do you identify the pattern for Kth Smallest Element in a Sorted Matrix?

Look for key signals in the prompt: "each row is sorted" indicates Every row is already a sorted list. We can merge the rows instead of sorting them all again.; "k-th smallest" indicates Only the first k values taken out in order matter. Stop after k pops.; "rows and columns both sorted" indicates Column 0 is sorted too, so the first cells of the rows let us decide how many rows to start..

Kth Smallest Element in a Sorted Matrix

Medium·LeetCode #378Basic Anchor

LeetCode

Jump:

30-Second Mental ModelK-way Merge — kth across sorted rows (min-heap of row fronts)

Complexity:O(N² log N)→O(K log min(N, K))

Key Insight

Treat each row as a sorted list. Keep a min-heap with one cell per row: the first cell of that row you have not used yet. The smallest cell in the heap is the next smallest value in the matrix. Take it out, then push the cell to its right in the same row. The next smallest value is always the front of some row.

Core Validity Invariant

The smallest unused value in the whole matrix is always the smallest front in the heap, because each row's unused cells are sorted and its front is the smallest of them.

Problem

You get an n × n matrix. Every row is sorted from smallest to largest, and every column is sorted from top to bottom. Values can repeat.

Return the k-th smallest value in the whole matrix. Repeats count as separate places: if the value 13 appears twice, the two copies take two places in the order.

Input

An n × n integer matrix matrix with sorted rows and columns, and an integer k.

Output

One integer: the k-th smallest value among all n² cells.

Example 1

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

Output: 13

Read all nine values in order: 1, 5, 9, 10, 11, 12, 13, 13, 15. The 8th one is 13.

Example 2

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

Output: -5

There is only one cell, so it is the 1st smallest.

Constraints

• n == matrix.length == matrix[i].length
• 1 ≤ n ≤ 300
• −10^9 ≤ matrix[i][j] ≤ 10^9
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order
• 1 ≤ k ≤ n^2
• Follow-up: Could you solve the problem with a constant memory (i.e., O(1) memory complexity)?
• Follow-up: Could you solve the problem in O(n) time complexity? (very advanced; not expected in interviews)

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Each row is sorted. Where could the smallest value in the whole matrix be?
2.
If I read the matrix row after row, is that one sorted list? Check it with the 9 and the 10 in the first example.
3.
Do I need every value in sorted order, or only the k-th one?
4.
After I use one cell from a row, which cell in that row could be the next candidate?
5.
When k is small, do I need to look at all n rows to find the answer?

Brute force approach

Idea

Put every cell into one list and sort it. The answer is the value at index k − 1. Sorting does the merging for us, but it also orders all n² values when we only need one of them.

Thinking process

1
Each row and each column is sorted, but that alone does not let me read the matrix in order. The simplest safe move is to sort everything.
2
Check on the first example: the nine values are 1, 5, 9, 10, 11, 13, 12, 13, 15. Sorted, they are 1, 5, 9, 10, 11, 12, 13, 13, 15. Index 7 (the 8th value) is 13.
3
Sorting n² values costs O(n² log n²). With n = 300 that is 90,000 values, and most of that order is never used.
4
Return sorted[k − 1].

Code & Implementation

brute.cpp

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        // Copy every cell into one list, then sort the whole list.
        vector<int> all;
        for (auto& row : matrix)
            for (int x : row) all.push_back(x);

        sort(all.begin(), all.end());
        // Position k - 1 is the k-th smallest value.
        return all[k - 1];
    }
};

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // Copy every cell into one list, then sort the whole list.
        List<Integer> all = new ArrayList<>();
        for (int[] row : matrix) {
            for (int x : row) {
                all.add(x);
            }
        }

        Collections.sort(all);
        // Position k - 1 is the k-th smallest value.
        return all.get(k - 1);
    }
}

from typing import List

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        # Copy every cell into one list, then sort the whole list.
        all_elements: List[int] = []
        for row in matrix:
            for x in row:
                all_elements.append(x)

        all_elements.sort()
        # Position k - 1 is the k-th smallest value.
        return all_elements[k - 1]

export function kthSmallest(matrix: number[][], k: number): number {
    // Copy every cell into one list, then sort the whole list.
    const all: number[] = [];
    for (const row of matrix) {
        for (const x of row) {
            all.push(x);
        }
    }

    all.sort((a, b) => a - b);
    // Position k - 1 is the k-th smallest value.
    return all[k - 1];
}

Complexity

Time O(N² log N)Space O(N²)

We copy n² values and sort all of them, even though only one position is read. It is correct, and it is a fine baseline, but it ignores that every row is already sorted.

Better approach

Why brute force is slow

Brute force sorts all n² values, so it spends most of its time ordering values that are bigger than the answer.

What repeated work are we doing?

Almost all of that sorting is on values that will never be read, because they are above the k-th smallest.

What information can we reuse?

A heap of size k keeps only the values that could still be among the k smallest. Each new cell costs O(log k) instead of a full sort.

New approach

Idea

Scan every cell once and keep a max-heap of at most k values. When it grows past k, pop the largest, because it cannot be one of the k smallest. At the end, the top of the heap is the k-th smallest.

Thinking process

1
Brute force keeps every value. But the answer is one value, and only k values can sit below it. So I only need to keep k values at a time.
2
A max-heap gives me the largest kept value in O(log k). That is the one to throw away when the heap is too big.
3
Check with k = 6 on the example. After cells 1, 5, 9, 10, 11, 13 the heap has six values and its top is 13. The next cell is 12. The heap grows to seven, so pop 13. The top is now 12.
4
At the end the heap holds the six smallest values, and its top is the largest of them, which is the 6th smallest: 12.

Visual

The heap is shown largest first, so the top (left) is the value that gets evicted first. Green = kept, red = evicted, blue = the cell being read. Cells: value(row,col).

Max-heap of the k smallestmatrix = [[1,5,9],[10,11,13],[12,13,15]], k = 6step 1/11

row 0

row 1

row 2

max-heap (size ≤ k)

State

k: 6
heap size: 0

Start with an empty max-heap that may hold at most k values

We read the matrix one cell at a time. The max-heap keeps the k smallest values seen so far, so its top is the largest of them.

Code & Implementation

better.cpp

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        // Max-heap: the top is the LARGEST value we are still keeping.
        priority_queue<int> keep;

        for (auto& row : matrix) {
            for (int x : row) {
                keep.push(x);
                // Only the k smallest values can be the answer, so drop the largest.
                if ((int)keep.size() > k) keep.pop();
            }
        }
        // The heap now holds the k smallest values. Its top is the largest of them.
        return keep.top();
    }
};

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // Max-heap: the top is the LARGEST value we are still keeping.
        PriorityQueue<Integer> keep = new PriorityQueue<>(Collections.reverseOrder());

        for (int[] row : matrix) {
            for (int x : row) {
                keep.offer(x);
                // Only the k smallest values can be the answer, so drop the largest.
                if (keep.size() > k) {
                    keep.poll();
                }
            }
        }
        // The heap now holds the k smallest values. Its top is the largest of them.
        return keep.peek();
    }
}

import heapq
from typing import List

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        # Max-heap: the top is the LARGEST value we are still keeping (negated).
        keep: List[int] = []

        for row in matrix:
            for x in row:
                heapq.heappush(keep, -x)
                # Only the k smallest values can be the answer, so drop the largest.
                if len(keep) > k:
                    heapq.heappop(keep)

        # The heap now holds the k smallest values. Its top is the largest of them.
        return -keep[0]

class PriorityQueue<T> {
    private heap: T[] = [];
    constructor(private compare: (a: T, b: T) => number) {}

    push(val: T): void {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop(): T | undefined {
        if (this.heap.length === 0) return undefined;
        const top = this.heap[0];
        const bottom = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = bottom;
            this.bubbleDown(0);
        }
        return top;
    }

    peek(): T | undefined {
        return this.heap[0];
    }

    size(): number {
        return this.heap.length;
    }

    isEmpty(): boolean {
        return this.heap.length === 0;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const p = (idx - 1) >> 1;
            if (this.compare(this.heap[idx], this.heap[p]) < 0) {
                [this.heap[idx], this.heap[p]] = [this.heap[p], this.heap[idx]];
                idx = p;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.heap.length;
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.compare(this.heap[left], this.heap[smallest]) < 0) {
                smallest = left;
            }
            if (right < len && this.compare(this.heap[right], this.heap[smallest]) < 0) {
                smallest = right;
            }
            if (smallest !== idx) {
                [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

export function kthSmallest(matrix: number[][], k: number): number {
    // Max-heap: the top is the LARGEST value we are still keeping.
    const keep = new PriorityQueue<number>((a, b) => b - a);

    for (const row of matrix) {
        for (const x of row) {
            keep.push(x);
            // Only the k smallest values can be the answer, so drop the largest.
            if (keep.size() > k) {
                keep.pop();
            }
        }
    }
    // The heap now holds the k smallest values. Its top is the largest of them.
    return keep.peek()!;
}

Complexity

Time O(N² log K)Space O(K)

This beats sorting when k is small, but it still reads all n² cells. The optimal approach only takes about k values out of the rows.

Optimized approach

Idea

Start from brute force

Brute force copies all cells, sorts them, and reads one position.

Find the repeated work

Sorting puts every cell in order, including the many cells far above the answer. The K-way merge only ever looks at the front cell of each row.

Define the state — what variables do I need?

heap: Min-heap of (value, row, col). Each row has at most one entry: its current front cell.
popped: How many values have been taken out so far. When it reaches k, the last value taken out is the answer.
col of a row: The column of that row's front. Taking out (r, c) moves row r's front to column c + 1.

Define validity

The smallest unused value in the whole matrix is always the smallest front in the heap, because each row's unused cells are sorted and its front is the smallest of them.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

Push matrix[r][0] for each row r < min(n, k)

These fronts are the only candidates for the smallest value. A row below the k-th one cannot hold a value below the answer.

Each of the k pops

Take out the smallest entry (v, r, c)

By the validity rule, v is the smallest unused value overall.

After a pop, if c + 1 < n

Push matrix[r][c + 1]

That is the new front of row r. Nothing to its left is unused, so nothing else in row r can be smaller.

After the k-th pop

Return the value just taken out

We have taken out the k smallest values in order, so the last one is the k-th smallest.

What does the current window add to the answer?

Each pop writes the next value of the matrix in sorted order. After k pops, the last value written is the k-th smallest.

Code & Implementation

optimal.cpp

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();

        // Heap entry: (value, row, col). A min-heap, so the smallest front comes out first.
        using Entry = tuple<int, int, int>;
        priority_queue<Entry, vector<Entry>, greater<Entry>> pq;

        // Each row's front starts at column 0. Column 0 is sorted top to bottom,
        // so a row below the k-th one can't hold anything smaller than the answer.
        for (int r = 0; r < min(n, k); r++) pq.push({matrix[r][0], r, 0});

        int value = 0;
        for (int pops = 0; pops < k; pops++) {
            auto [v, r, c] = pq.top();
            pq.pop();
            value = v;   // after k pops, the last value taken out is the answer

            // The next cell in the same row becomes that row's new front.
            // Stop at the end of the row.
            if (c + 1 < n) pq.push({matrix[r][c + 1], r, c + 1});
        }
        return value;
    }
};

import java.util.PriorityQueue;

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

        // Heap entry: [value, row, col]. A min-heap, so the smallest front comes out first.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

        // Each row's front starts at column 0. Column 0 is sorted top to bottom,
        // so a row below the k-th one can't hold anything smaller than the answer.
        int limit = Math.min(n, k);
        for (int r = 0; r < limit; r++) {
            pq.offer(new int[]{matrix[r][0], r, 0});
        }

        int value = 0;
        for (int pops = 0; pops < k; pops++) {
            int[] top = pq.poll();
            int v = top[0];
            int r = top[1];
            int c = top[2];
            value = v;   // after k pops, the last value taken out is the answer

            // The next cell in the same row becomes that row's new front.
            // Stop at the end of the row.
            if (c + 1 < n) {
                pq.offer(new int[]{matrix[r][c + 1], r, c + 1});
            }
        }
        return value;
    }
}

import heapq
from typing import List, Tuple

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)

        # Heap entry: (value, row, col). A min-heap, so the smallest front comes out first.
        pq: List[Tuple[int, int, int]] = []

        # Each row's front starts at column 0. Column 0 is sorted top to bottom,
        # so a row below the k-th one can't hold anything smaller than the answer.
        for r in range(min(n, k)):
            heapq.heappush(pq, (matrix[r][0], r, 0))

        value = 0
        for _ in range(k):
            v, r, c = heapq.heappop(pq)
            value = v   # after k pops, the last value taken out is the answer

            # The next cell in the same row becomes that row's new front.
            # Stop at the end of the row.
            if c + 1 < n:
                heapq.heappush(pq, (matrix[r][c + 1], r, c + 1))

        return value

class PriorityQueue<T> {
    private heap: T[] = [];
    constructor(private compare: (a: T, b: T) => number) {}

    push(val: T): void {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop(): T | undefined {
        if (this.heap.length === 0) return undefined;
        const top = this.heap[0];
        const bottom = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = bottom;
            this.bubbleDown(0);
        }
        return top;
    }

    peek(): T | undefined {
        return this.heap[0];
    }

    size(): number {
        return this.heap.length;
    }

    isEmpty(): boolean {
        return this.heap.length === 0;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const p = (idx - 1) >> 1;
            if (this.compare(this.heap[idx], this.heap[p]) < 0) {
                [this.heap[idx], this.heap[p]] = [this.heap[p], this.heap[idx]];
                idx = p;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.heap.length;
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.compare(this.heap[left], this.heap[smallest]) < 0) {
                smallest = left;
            }
            if (right < len && this.compare(this.heap[right], this.heap[smallest]) < 0) {
                smallest = right;
            }
            if (smallest !== idx) {
                [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

export function kthSmallest(matrix: number[][], k: number): number {
    const n = matrix.length;

    // Heap entry: [value, row, col]. A min-heap, so the smallest front comes out first.
    const pq = new PriorityQueue<[number, number, number]>((a, b) => a[0] - b[0]);

    // Each row's front starts at column 0. Column 0 is sorted top to bottom,
    // so a row below the k-th one can't hold anything smaller than the answer.
    const limit = Math.min(n, k);
    for (let r = 0; r < limit; r++) {
        pq.push([matrix[r][0], r, 0]);
    }

    let value = 0;
    for (let pops = 0; pops < k; pops++) {
        const [v, r, c] = pq.pop()!;
        value = v;   // after k pops, the last value taken out is the answer

        // The next cell in the same row becomes that row's new front.
        // Stop at the end of the row.
        if (c + 1 < n) {
            pq.push([matrix[r][c + 1], r, c + 1]);
        }
    }
    return value;
}

Complexity

Time O(K log min(N, K))Space O(min(N, K))

We seed at most min(n, k) cells and take values out k times. Each heap operation costs O(log min(n, k)). A different route is a binary search on the value range: for a guess mid, count how many cells are at most mid by walking a staircase from the bottom-left corner in O(n). That gives O(n log(max − min)). Both are correct; the heap is the one that teaches this pattern.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Copy all n² values into one list, sort it, and read position k	O(N² log N)	O(N²)
Better	Scan every cell and keep a max-heap of the k smallest seen; its top is the answer	O(N² log K)	O(K)
Optimal	Min-heap with one front cell per row; take k values out and push the cell to the right	O(K log min(N, K))	O(min(N, K))

Why does this belong to this pattern?

Clues in the problem statement

“each row is sorted”Every row is already a sorted list. We can merge the rows instead of sorting them all again.
“k-th smallest”Only the first k values taken out in order matter. Stop after k pops.
“rows and columns both sorted”Column 0 is sorted too, so the first cells of the rows let us decide how many rows to start.

k sorted lists+k-th smallest across all of them+min-heap of one front per list→K-way Merge — kth across sorted rows (min-heap of row fronts)

This is the anchor of the Kth-across sub-pattern. The rows are sorted lists, so the next smallest value is always the front of some row, and a heap finds it. Unlike Top K, the heap is not a filter on all values: it holds one cell per row, and the pops themselves put the values in order. The next question keeps the same heap but the lists are the pairs of two arrays.

Don't make this mistake

Treating the matrix as one sorted list, row after row (pattern confusion)

✗ return matrix[(k - 1) / n][(k - 1) % n];

✓ Take values out of a K-way merge k times, as in the optimal approach.

Rows are sorted, but row 1 does not continue where row 0 stops. On [[1,5,9],[10,11,13],[12,13,15]] with k = 6, the formula reads matrix[1][2] = 13. The correct answer is 12, which sits in row 2. Row 2's first cell is smaller than the end of row 1, so a row-by-row count skips it.

Using a max-heap for the K-way merge (comparator direction)

✗ priority_queue<tuple<int, int, int>> pq;

✓ priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

A default priority_queue pops the largest value first. Seeded with the fronts 1, 10 and 12, the first pop is 12 (row 2), not 1, so the values come out from the largest end and the answer is wrong.

No bounds check on the cell to the right

✗ pq.push({matrix[r][c + 1], r, c + 1});

✓ if (c + 1 < n) pq.push({matrix[r][c + 1], r, c + 1});

When a row's last cell is taken out, c + 1 = n is past the end of the row. The read is out of bounds, and the heap gets a garbage value.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like K-way Merge translate into production architectures and low-level memory mechanics.

LLD Architecture