Log inSign up
mediumLeetCodeNot Started

Kth Smallest Element in a Sorted Matrix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k-th smallest element in the matrix.

Note that it is the k-th smallest element in sorted order, not the k-th distinct element.

Find a solution with memory complexity better than O(n2).

Example 1 · Example 1: 3x3 Matrix:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: All elements sorted: [1, 5, 9, 10, 11, 12, 13, 13, 15]. The 8th smallest element is 13. Min-Heap (Initial Column): (1, [0,0]) / \ (10, [1,0]) (12, [2,0])

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 300
  • -109 <= matrix[i][j] <= 109
  • All rows and columns of matrix are sorted in non-decreasing order.
  • 1 <= k <= n2

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master Binary Search on an answer space (value range) rather than index range.
  • Understand the O(N) staircase counting technique in 2D sorted grids.
  • Implement both Min-Heap K-way merge and Binary Search solutions.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • 2D Matrix sorted both row-wise and column-wise.
  • Find Kth smallest or median element.
  • Space complexity constraint better than O(N2).

Algorithmic Decision Tree:

  • Min-Heap gives O(K log N) time and O(N) space (great for small K).
  • Binary Search on value range gives O(N log(max - min)) time and O(1) space (optimal for arbitrary K).

Connected Patterns:

Find K Pairs with Smallest SumsSearch a 2D Matrix IIKth Smallest Number in Multiplication Table

1. Brute Force — Flatten Matrix & Sort

Intuition

Copy all N2 elements into a 1D vector. Sort the vector ascending and return the element at index k-1.

When to apply: When simplicity is preferred and matrix size is small (n <= 50).

Algorithm

  1. Step 1: Flatten matrix into a 1D array.
  2. Step 2: Sort the array ascending.
  3. Step 3: Return array[k - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 int kthSmallest(vector<vector<int>>& matrix, int k) {
9 vector<int> flat;
10 for (auto& row : matrix) {
11 for (int val : row) flat.push_back(val);
12 }
13 sort(flat.begin(), flat.end());
14 return flat[k - 1];
15 }
16};
17
18int main() {
19 Solution sol;
20 vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
21 cout << "Kth Smallest (Brute Force): " << sol.kthSmallest(matrix, 8) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N^2 log(N^2)) — O(N2 log N) comparison sort.
  • Space complexity: O(N^2) — O(N2) storage.

Why Brute Force Doesn't Scale:

For n = 300, N2 = 90,000. Heap takes O(K log N) which is ~90,000 * 9 ops. Binary search takes 300 * 32 = ~9,600 ops (100x faster) and uses 0 extra memory.

Binary search runs in ~0.5ms with 0 memory allocations.

2. Better — Min-Heap (K-Way Merge)

Intuition

Each row of the matrix is a sorted list. Insert the first element of the first min(N, K) rows into a Min-Heap. In each iteration, pop the minimum element and push the next element from that same row. After k pops, the popped element is the kth smallest.

When to apply: When K is much smaller than N2.

Algorithm

  1. Step 1: Initialize Min-Heap with (matrix[r][0], r, 0) for r from 0 to min(n, k) - 1.
  2. Step 2: Loop k times:
  3. Step 3: Pop (val, r, c).
  4. Step 4: If c + 1 < n, push (matrix[r][c + 1], r, c + 1).
  5. Step 5: Return the val from the kth pop.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <tuple>
5using namespace std;
6
7class Solution {
8public:
9 int kthSmallest(vector<vector<int>>& matrix, int k) {
10 int n = matrix.size();
11 using Element = tuple<int, int, int>; // val, r, c
12 priority_queue<Element, vector<Element>, greater<Element>> minHeap;
13
14 int limit = min(n, k);
15 for (int r = 0; r < limit; r++) {
16 minHeap.push({matrix[r][0], r, 0});
17 }
18
19 int result = 0;
20 for (int i = 0; i < k; i++) {
21 auto [val, r, c] = minHeap.top();
22 minHeap.pop();
23 result = val;
24
25 if (c + 1 < n) {
26 minHeap.push({matrix[r][c + 1], r, c + 1});
27 }
28 }
29 return result;
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
36 cout << "Kth Smallest (Min-Heap): " << sol.kthSmallest(matrix, 8) << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(K log(min(N, K))) — O(K log(min(N, K))) heap time.
  • Space complexity: O(min(N, K)) — O(min(N, K)) auxiliary space.

3. Optimal — Binary Search on Value Range (O(1) Space)

Intuition

Set low = matrix[0][0], high = matrix[n-1][n-1]. For mid, start at bottom-left corner (r = n-1, c = 0). If matrix[r][c] <= mid, all elements in column c up to r are <= mid (add r + 1 to count, c++). Else r--. If count < k, low = mid + 1; else high = mid.

When to apply: Standard optimal solution with strict O(1) auxiliary memory.

Algorithm

  1. Step 1: Set low = matrix[0][0], high = matrix[n - 1][n - 1].
  2. Step 2: While low < high: mid = low + (high - low) / 2.
  3. Step 3: Count elements <= mid: start r = n - 1, c = 0. While r >= 0 and c < n: if matrix[r][c] <= mid, count += r + 1, c++; else r--.
  4. Step 4: If count < k, low = mid + 1; else high = mid.
  5. Step 5: Return low.

Interactive Trace for Kth Smallest Element in a Sorted Matrix

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Heap initialized with first element from each row: (1, [0,0]), (10, [1,0]), (12, [2,0])
Visual state
Values and pointers at this exact step
tree
Root: 1
1
Child: 10
10
Child: 12
12

Node order shown; add connections to display explicit tree edges.

pop: m1
Check / comparison
Pop 1, push next in row: 5 at (0,1).
Decision / next transition
Heap becomes [5, 10, 12].
Why this step matters

Step 1: Heap initialized with first element from each row: (1, [0,0]), (10, [1,0]), (12, [2,0]).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6 int countLessOrEqual(const vector<vector<int>>& matrix, int mid, int n) {
7 int count = 0;
8 int r = n - 1, c = 0;
9 while (r >= 0 && c < n) {
10 if (matrix[r][c] <= mid) {
11 count += (r + 1);
12 c++;
13 } else {
14 r--;
15 }
16 }
17 return count;
18 }
19
20public:
21 int kthSmallest(vector<vector<int>>& matrix, int k) {
22 int n = matrix.size();
23 int low = matrix[0][0];
24 int high = matrix[n - 1][n - 1];
25
26 while (low < high) {
27 int mid = low + (high - low) / 2;
28 if (countLessOrEqual(matrix, mid, n) < k) {
29 low = mid + 1;
30 } else {
31 high = mid;
32 }
33 }
34 return low;
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
41 cout << "Kth Smallest (Optimal Binary Search): " << sol.kthSmallest(matrix, 8) << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N log(max - min)) — O(N log(max - min)) time.
  • Space complexity: O(1) — O(1) strictly constant extra space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Flatten Matrix & SortO(N^2 log(N^2))O(N^2)Copy all elements into a 1D array, sort ascending, and return element at index k - 1.Storing and sorting all N2 elements.
2.Better — Min-Heap (K-Way Merge)O(K log(min(N, K)))O(min(N, K))Treat each row as a sorted linked list. Push first element of each row into Min-Heap. Pop and advance column.Heap operations for K items.
3.Optimal — Binary Search on Value Range + Staircase CountOptimalO(N log(max - min))O(1)Binary search on values in [matrix[0][0], matrix[n-1][n-1]]. Count elements <= mid in O(N) using staircase search.None. Optimal.

Common Pitfalls & Crucial Edge Cases

Binary search on indices instead of value range

Matrix indices are 2D; binary searching on values is required.

Using high = mid - 1

When count >= k, mid itself might be the answer; must set high = mid.

Thinking mid might not be in the matrix

Because we shrink whenever count >= k, low converges to the smallest value with at least k elements <= it, which is guaranteed to be in the matrix.

Crucial Edge Cases to Validate:

  • k == 1 — Returns matrix[0][0].
  • k == n * n — Returns matrix[n-1][n-1].
  • Negative values — Binary search operates properly over negative integer ranges.
  • Large duplicate values — Condition high = mid ensures convergence on the actual matrix element.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast the Min-Heap approach (optimal for small K) with Binary Search on Value Range (optimal for arbitrary K and O(1) space).
  2. Explain the staircase counting trick starting at bottom-left.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the final value of low guaranteed to be an actual element inside the matrix?

Back to DSA Sheet