Skip to main content

378. Kth Smallest Element in a Sorted Matrix

medium

Find the kth smallest element in an n x n matrix where rows and columns are individually sorted. Binary-search on value gives you O(n log(max - min)) — heap-only candidates miss this gear.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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. You must find a solution with a memory complexity better than O(n^2).

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

Examples

Example 1

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

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Heap solutions exist but they don't beat the matrix-walk binary-search-on-value approach in both time and memory.

Hint 2

Binary search the value range [matrix[0][0], matrix[n-1][n-1]]. For a midpoint v, count how many entries in the matrix are <= v.

Hint 3

Count entries <= v in O(n) by walking from the bottom-left: move right when entry <= v, otherwise move up.

Solution approach

Reveal approach

Binary search on the value range, not on indices. Set lo = matrix[0][0] and hi = matrix[n-1][n-1]. While lo < hi, compute mid = lo + (hi - lo) / 2. Count how many matrix entries are <= mid in O(n) using the staircase walk: start at row = n - 1, col = 0; if matrix[row][col] <= mid, all entries in that column above are also <= mid, so add row + 1 to count and move col right; otherwise move row up. After the walk, if count < k the answer is > mid (lo = mid + 1), otherwise hi = mid. When lo == hi, return lo — that value is guaranteed to be in the matrix because it's the smallest value with rank >= k. O(n log(max - min)) time, O(1) extra space, well under the O(n^2) memory floor the problem warns about.

Complexity

Time
O(n log(max - min))
Space
O(1)

Related patterns

  • binary-search
  • binary-search-on-answer
  • matrix

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Apple

Practice these live with InterviewChamp.AI

Drill Kth Smallest Element in a Sorted Matrix and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →