Coding Interview PatternsKth Smallest Element in a Sorted Matrix
MediumK-way Merge

Kth Smallest Element in a Sorted Matrix

Explanation & Solution

Practice Problem

Description

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

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

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

Output: 13

Explanation: The elements in sorted order are [1, 5, 9, 10, 11, 12, 13, 13, 15], and the 8th smallest is 13.

Constraints

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • All rows and columns are sorted in non-decreasing order.
  • 1 <= k <= n^2

Approach

K-way Merge pattern

1. Define the Search Range

  • The smallest possible value is matrix[0][0] (top-left corner).
  • The largest possible value is matrix[n-1][n-1] (bottom-right corner).
  • We binary search on the value range rather than on indices.

2. Binary Search on Value

  • Compute mid = lo + Math.floor((hi - lo) / 2).
  • Count how many elements in the matrix are less than or equal to mid.
  • If the count is less than k, the kth smallest must be larger, so set lo = mid + 1.
  • Otherwise, the kth smallest could be mid or smaller, so set hi = mid.

3. Count Elements ≤ Target Efficiently

  • Start from the bottom-left corner (row = n-1, col = 0).
  • If matrix[row][col] <= target, then all elements above in this column are also ≤ target, so add row + 1 to the count and move right (col++).
  • If matrix[row][col] > target, move up (row--).
  • This traversal counts all qualifying elements in O(n) time.

4. Convergence

  • The loop ends when lo === hi. At this point, lo is the smallest value in the matrix such that at least k elements are ≤ lo.
  • This value is guaranteed to exist in the matrix because we are converging on actual matrix values.

Key Insight

  • The core idea is that binary searching on the value space (not indices) and using the sorted row-column structure to count elements efficiently avoids the need to flatten or sort the entire matrix.
Time
O(n · log(max − min)) — binary search over the value range with an O(n) count at each step.
Space
O(1)only a few variables are used.

Visualization

Input:
DFS Traversal3×3 grid
012012159101113121315
output—

Press play to start dfs traversal

CurrentQueuedVisitedSource
57 steps

Solution Code

Previous
Merge K Sorted Lists
Next
Find K Pairs with Smallest Sums