Kth Smallest Element in a Sorted Matrix

LeetCode 378: Kth Smallest Element in a Sorted Matrix Solution & Explanation

Problem Overview

TL;DR: The optimal pattern-based solution treats the matrix rows as independent sorted lists and uses a Min-Heap to perform a K-way merge, extracting the smallest available element $k$ times.

The problem asks us to find the $k$-th smallest number within an $n \times n$ matrix. The critical property of this matrix is that every row and every column is sorted in ascending order. We are not looking for the $k$-th distinct value, but simply the element at the $k$-th position if all elements were collected and sorted. We must achieve this with memory complexity better than $O(n^2)$.

This is a popular interview question because it tests the ability to leverage sorted properties in multi-dimensional data structures, specifically targeting LeetCode 378.

Brute Force Approach for Kth Smallest Element in a Sorted Matrix

The most straightforward approach ignores the matrix structure entirely and treats the input as a collection of $n^2$ numbers.

1. Traverse the entire matrix and collect all $n \times n$ elements into a single list.
2. Sort this new list in ascending order.
3. Return the element at index $k-1$.

Pseudo-code:

function bruteForce(matrix, k):
    list = []
    for row in matrix:
        for val in row:
            list.add(val)
    sort(list)
    return list[k-1]

Complexity Analysis:

• Time Complexity: $O(N \log N)$ where $N$ is the total number of elements ($n^2$). This expands to $O(n^2 \log(n^2))$, which simplifies to $O(n^2 \log n)$.
• Space Complexity: $O(n^2)$ to store the flattened list.

Why it fails: While this solution produces the correct answer, it fails the specific problem constraint requiring memory complexity better than $O(n^2)$. Furthermore, it is inefficient because it completely ignores the fact that rows and columns are already sorted, performing a redundant full sort.

Algorithm Strategy: Heap (Priority Queue) Patterns

1. Initialization: Create a Min-Heap to store tuples of (value, row_index, col_index).
2. Populate Frontier: Insert the first element of each of the $n$ rows into the heap. This represents the initial frontier of smallest candidates.
3. Iterative Extraction:
   • Loop $k-1$ times.
   • In each iteration, pop the smallest element (the root) from the heap.
   • Identify the row_index and col_index of the popped element.
   • If there is a next element in that same row (i.e., col_index + 1 < n), push that next element into the heap.
4. Result: After the loop finishes, the element currently at the top of the heap is the $k$-th smallest element.

This strategy ensures we strictly follow the sorted order without sorting the entire matrix or storing all elements.

Execution Flow

Let's trace the logic with a simple example: matrix = [[1,5,9], [10,11,13], [12,13,15]], k = 4.

1. Initialize Heap:

   • Push (1, 0, 0), (10, 1, 0), (12, 2, 0).
   • Heap: [(1,0,0), (10,1,0), (12,2,0)] (ordered by value).

2. Iteration 1 (Find 1st smallest):

   • Pop (1, 0, 0).
   • Next in row 0 is matrix[0][1] which is 5.
   • Push (5, 0, 1).
   • Heap: [(5,0,1), (10,1,0), (12,2,0)].

3. Iteration 2 (Find 2nd smallest):

   • Pop (5, 0, 1).
   • Next in row 0 is matrix[0][2] which is 9.
   • Push (9, 0, 2).
   • Heap: [(9,0,2), (10,1,0), (12,2,0)].

4. Iteration 3 (Find 3rd smallest):

   • Pop (9, 0, 2).
   • Row 0 is exhausted (col index 2 is max). Do not push.
   • Heap: [(10,1,0), (12,2,0)].

5. Final Step (Find 4th smallest):

   • The loop for $k-1$ iterations is done.
   • The top of the heap is (10, 1, 0).
   • Return 10.

Proof of Correctness

The correctness relies on the sorted property of the rows. At any step $t$, the Min-Heap contains the smallest unvisited element from every row that still has elements.

Let $S$ be the set of elements currently in the heap. Let $U$ be the set of elements already popped. The logic dictates that any element $x$ remaining in the matrix (not in $S$ or $U$) is strictly greater than or equal to at least one element in $S$ (specifically, the element in $S$ belonging to the same row as $x$, because rows are sorted).

Therefore, the minimum element in $S$ is guaranteed to be smaller than or equal to any other element in the matrix that hasn't been visited yet. By extracting the minimum $k$ times, we are guaranteed to traverse the elements in non-decreasing order.

Pattern Reuse Notes

The Heap - K-way Merge pattern used in this LeetCode 378 Solution is a fundamental technique for interview preparation. It applies directly to:

• LeetCode 23: Merge k Sorted Lists - Identical logic; instead of matrix rows, you merge linked lists.
• LeetCode 373: Find K Pairs with Smallest Sums - Treats pairs as a virtual matrix where rows are implicit sorted lists.
• LeetCode 632: Smallest Range Covering Elements from K Lists - Uses the same heap structure to track the minimum of the current range window.

Reference Implementation

C++ Solution for LeetCode 378

1#include <vector>
2#include <queue>
3#include <tuple>
4
5using namespace std;
6
7class Solution {
8public:
9    int kthSmallest(vector<vector<int>>& matrix, int k) {
10        int n = matrix.size();
11        
12        // Min-Heap stores tuples: {value, row_index, col_index}
13        // priority_queue is a Max-Heap by default, so we use greater<> for Min-Heap behavior.
14        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> minHeap;
15        
16        // Step 1: Initialize heap with the first element of each row
17        // We take min(n, k) because the answer cannot be in a row index >= k
18        for (int r = 0; r < min(n, k); ++r) {
19            minHeap.push({matrix[r][0], r, 0});
20        }
21        
22        // Step 2: Extract min k-1 times to reach the k-th element
23        for (int i = 0; i < k - 1; ++i) {
24            auto [val, r, c] = minHeap.top();
25            minHeap.pop();
26            
27            // If the current row has more elements, push the next one
28            if (c + 1 < n) {
29                minHeap.push({matrix[r][c + 1], r, c + 1});
30            }
31        }
32        
33        // The top of the heap is now the k-th smallest element
34        return get<0>(minHeap.top());
35    }
36};

Java Solution for LeetCode 378

1import java.util.PriorityQueue;
2
3class Solution {
4    public int kthSmallest(int[][] matrix, int k) {
5        int n = matrix.length;
6        
7        // Min-Heap stores int[] where: {value, row_index, col_index}
8        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
9        
10        // Step 1: Initialize heap with the first element of each row
11        // We optimize by only checking min(n, k) rows
12        for (int r = 0; r < Math.min(n, k); r++) {
13            minHeap.offer(new int[]{matrix[r][0], r, 0});
14        }
15        
16        // Step 2: Extract min k-1 times
17        for (int i = 0; i < k - 1; i++) {
18            int[] current = minHeap.poll();
19            int r = current[1];
20            int c = current[2];
21            
22            // If the current row has a next element, add it to the heap
23            if (c + 1 < n) {
24                minHeap.offer(new int[]{matrix[r][c + 1], r, c + 1});
25            }
26        }
27        
28        // The root of the heap is the k-th smallest element
29        return minHeap.peek()[0];
30    }
31}

Python Solution for LeetCode 378

1import heapq
2
3class Solution:
4    def kthSmallest(self, matrix: list[list[int]], k: int) -> int:
5        n = len(matrix)
6        min_heap = []
7        
8        # Step 1: Initialize heap with the first element of each row.
9        # Python's heapq maintains a min-heap by default.
10        # We store tuples (value, row_index, col_index)
11        for r in range(min(n, k)):
12            heapq.heappush(min_heap, (matrix[r][0], r, 0))
13            
14        # Step 2: Pop the smallest element k-1 times
15        for _ in range(k - 1):
16            val, r, c = heapq.heappop(min_heap)
17            
18            # If there is a next element in the current row, push it
19            if c + 1 < n:
20                heapq.heappush(min_heap, (matrix[r][c + 1], r, c + 1))
21                
22        # The top of the heap is the k-th smallest element
23        return min_heap[0][0]