← DSA Atlas
Dedicated problem page · #378

Kth Smallest Element in a Sorted Matrix

MediumBinary SearchBinary search on the answer valueBinary search on value range with a counting predicate
Solve on LeetCode ↗
378
MediumBinary SearchBinary search on value range with a counting predicateBinary search on the answer value

Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each row and each column is sorted in ascending order, return the kth smallest element in the matrix by sorted order (counting duplicates), not the kth distinct element.

Open official problem prompt ↗
In plain English

Find the value that occupies rank k when all matrix entries are considered in sorted order.

Picture it like this

Guessing a price in a bounded range: you name a number, an assistant tells you how many items cost that much or less, and you adjust your guess until exactly k items are at or below it.

Example
Input
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output
13
Why
Sorted, the values are 1,5,9,10,11,12,13,13,15; the 8th is 13.
Constraints
n == matrix.length == matrix[i].length1 <= n <= 300-10^9 <= matrix[i][j] <= 10^9All rows and all columns are sorted ascending1 <= k <= n^2
Pattern lesson

See the pattern, then code

Binary search on the answer value
Recognition clue

'Kth smallest' over a matrix sorted both ways where a full sort or heap feels heavy hints at binary-searching the numeric value and counting how many entries fall below it.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. For a candidate value x you can count entries <= x in O(n) using a staircase walk from the bottom-left corner. The count is non-decreasing in x, so binary-search the smallest x whose count reaches k — that x is guaranteed to be an actual matrix value.

New words, made simpleKnow these before the algorithm
Binary search on the answer
Searching over possible result values, not array indices
Counting predicate
A function returning how many elements satisfy <= x, monotonic in x
Staircase walk
Traversing a doubly sorted matrix from a corner to count in O(n)
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Flatten and sort

Simple but ignores the sorted structure and uses quadratic memory.

Copy all n^2 entries into a list, sort, and index k-1.

Time O(n^2 log n)Space O(n^2)
Min-heap merge of rows

Good, but slower when k is near n^2.

Push row heads into a heap and pop k times, pushing the next in each row.

Time O(k log n)Space O(n)
Best choiceBinary search on value with counting

Fastest for large k and uses constant extra space.

Search the value range; count elements <= mid with a corner walk to steer the bounds.

Time O(n log(max - min))Space O(1)
The rule we keep true

Invariant

The answer always lies in [lo, hi], and count_le is monotonically non-decreasing, so the smallest value with count_le >= k is well defined.

Why this is correct

Reasoning

The count of entries <= x rises monotonically with x, so 'count_le(x) >= k' is a monotonic predicate; binary search finds its first true value. Because the count only reaches k exactly at a value present in the matrix (the count jumps at real entries), the returned lo is guaranteed to be an actual element, not a gap value.

The algorithm in three movesSay these aloud before coding
1Set lo = matrix[0][0] and hi = matrix[n-1][n-1]

lo=1 hi=15 mid=8 -> count(<=8)=2 < 8, lo=9

2For mid, count elements <= mid by walking from bottom-left

lo=9 hi=15 mid=12 -> count(<=12)=6 < 8, lo=13

3If the count is less than k, raise lo to mid + 1

lo=13 hi=15 mid=14 -> count(<=14)=8 >= 8, hi=14

4Otherwise lower hi to mid

lo=13 hi=14 mid=13 -> count(<=13)=8 >= 8, hi=13; lo==hi=13

5Return lo, which lands on a real matrix element

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
51
92
103
114
135
126
137
158
1 · Readlo=1, hi=15
2 · AskHow many entries <= 8?
3 · Update statemid=8, count=2
4 · Result2 < 8, so lo = 9
Key takeaway

Counting values <= mid drives the range down to the true 8th smallest, 13.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-12Count entries <= x

    Start at bottom-left; if the cell fits, the whole column above it does too, so add row+1 and move right, else move up.

  2. 2
    Lines 13Value bounds

    The answer lies between the smallest and largest matrix values.

  3. 3
    Lines 14-19Search the value

    Too few entries means raise lo; enough means keep mid as an upper bound.

  4. 4
    Lines 20Return the ranked value

    lo lands exactly on the kth smallest, a real matrix entry.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k = 1 (the minimum, matrix[0][0])
  • k = n^2 (the maximum)
  • Many duplicate values across cells
  • 1 x 1 matrix
!

Common beginner mistakes

  • Counting distinct values instead of counting with multiplicity
  • Walking from the wrong corner so the column/row shortcut is invalid
  • Using count_le(mid) <= k instead of < k, which returns the wrong rank
Check your understanding

Why is the returned lo guaranteed to be an element that actually appears in the matrix?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search