Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Kth Smallest Element in a Sorted Matrix

Find the k-th smallest value in a grid with sorted rows and columns by binary searching on the value and counting smaller entries with a staircase walk.

hardPattern: Matrix Search

Updated Long read: 11 min read

Approaches at a glance

ApproachTimeSpace
Flatten and sortO(n² log n)O(n²)
Binary search on the value with a staircase countO(n log(max − min))O(1)

The problem

You are given a square grid of integers, n rows by n columns. Every row is sorted in ascending order from left to right and every column is sorted in ascending order from top to bottom. You are also given a number k, between 1 and n × n.

Imagine writing all the values out in one sorted list, keeping repeats. Return the value in position k of that list, counting from 1. Repeated values each take up their own position: the answer is the k-th entry, not the k-th different value. The aim is to do it without building that list, using less than O(n²) extra memory.

grid =
   1   4   9
   3   7  12
   8  11  15
 
sorted: 1, 3, 4, 7, 8, 9, 11, 12, 15
 
k = 5   →  8
k = 1   →  1
k = 9   →  15
 
grid =
   1   2
   2   3
 
sorted: 1, 2, 2, 3
k = 3   →  2     (the second 2 counts as its own entry)

Approach 1: flatten and sort

Do exactly what the problem describes: put every value in one list, sort it, and read off position k.

JavaScript

function kthSmallestInMatrixBySorting(grid, k) {
  const values = [];
  for (const row of grid) {
    for (const value of row) values.push(value);
  }
  values.sort((a, b) => a - b);
  return values[k - 1];
}

Python

def kth_smallest_in_matrix_by_sorting(grid, k):
    values = []
    for row in grid:
        values.extend(row)
    values.sort()
    return values[k - 1]

The comparison function in the JavaScript version matters. Without it, sort compares numbers as text, and 10 lands before 9.

Time O(n² log n): there are n² values, and sorting them costs O(n² log n²), which is the same thing since log n² is 2 log n. Space O(n²) for the copy. It is correct and a fine thing to write first, but it treats the grid as a bag of numbers and throws away the ordering it arrived with.

Turning the question round

The direct question, "which value is in position k?", is hard to answer without sorting. The reverse question is easy:

Given some number x, how many values in the grid are less than or equal to x?

Call that countAtMost(x). For the first grid above, countAtMost(8) is 5, because 1, 3, 4, 7 and 8 qualify.

Now watch what happens to that count as x grows:

x 0 1 2 3 4 5 6 7 8 9 10 11
countAtMost(x) 0 1 1 2 3 3 3 4 5 6 6 7
At least 5? No No No No No No No No Yes Yes Yes Yes

The count never goes down, so the bottom row is a run of "No" followed by a run of "Yes". The k-th smallest value is the first x that gets a "Yes": the smallest number with at least k grid values at or below it.

A row of answers that flips from "No" to "Yes" exactly once is what binary search needs. This is binary search on the answer, the same idea as in Koko Eating Bananas: search the range of possible answers, not the positions in an array. Here the possible answers run from the smallest value in the grid (top-left) to the largest (bottom-right).

Two things are needed to make it work: a fast countAtMost, and an argument that the search lands on a value that is really in the grid.

Counting with a staircase

In any one row, the values less than or equal to x form a block at the left end, because the row is sorted. Moving down a row, every value is at least as large as the one above it, so the block can only stay the same length or get shorter. The right-hand edge of the blocks is therefore a staircase that steps left as it goes down.

Values ≤ 8 are in brackets:
 
  [1]  [4]   9
  [3]  [7]  12
  [8]  11   15

So one column pointer can serve every row. Start it at the last column. In each row, move it left while it points at something larger than x. Where it stops, it and everything to its left qualify, which is col + 1 cells. Carry the pointer to the next row as it is, never moving it back to the right.

JavaScript

// How many values in the grid are less than or equal to limit.
function countAtMost(grid, limit) {
  let col = grid[0].length - 1;
  let count = 0;
 
  for (let row = 0; row < grid.length; row++) {
    while (col >= 0 && grid[row][col] > limit) col--;
    count += col + 1;
  }
  return count;
}

Python

# How many values in the grid are less than or equal to limit.
def count_at_most(grid, limit):
    col = len(grid[0]) - 1
    count = 0
 
    for row in grid:
        while col >= 0 and row[col] > limit:
            col -= 1
        count += col + 1
    return count

The inner while looks as if it could make this slow, but col only ever decreases, so across the whole call it moves at most n times. One count is O(n), having read at most 2n of the n² cells. This is the counting staircase from the matrix search pattern, and close kin to the walk in Search a 2D Matrix II.

Approach 2: binary search on the value

JavaScript

function kthSmallestInMatrix(grid, k) {
  const n = grid.length;
  let lo = grid[0][0];                         // smallest value in the grid
  let hi = grid[n - 1][grid[0].length - 1];    // largest value in the grid
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (countAtMost(grid, mid) >= k) {
      hi = mid;       // enough values at or below mid: the answer is mid or smaller
    } else {
      lo = mid + 1;   // too few: the answer is larger than mid
    }
  }
  return lo;
}

Python

def kth_smallest_in_matrix(grid, k):
    lo = grid[0][0]     # smallest value in the grid
    hi = grid[-1][-1]   # largest value in the grid
 
    while lo < hi:
        mid = lo + (hi - lo) // 2
 
        if count_at_most(grid, mid) >= k:
            hi = mid      # enough values at or below mid: the answer is mid or smaller
        else:
            lo = mid + 1  # too few: the answer is larger than mid
    return lo

This is the lower-bound template: hi = mid keeps a passing candidate in play, lo = mid + 1 discards a failing one, and the loop ends when the two meet. The midpoint is rounded down with Math.floor in JavaScript and // in Python. Both round towards negative infinity, so grids with negative values work too. Math.trunc would not be safe here.

Walkthrough

The three-by-three grid from the top of the page, k = 5. The smallest value is 1 and the largest is 15.

lo hi mid countAtMost(mid) At least 5? Action
1 15 8 5 Yes hi = 8
1 8 4 3 No lo = 5
5 8 6 3 No lo = 7
7 8 7 4 No lo = 8
8 8 lo equals hi: return 8

And inside the first of those steps, countAtMost(grid, 8):

Row Row values col moves col ends at Added count
0 1, 4, 9 2 → 1 (9 is too large) 1 2 2
1 3, 7, 12 stays (7 is fine) 1 2 4
2 8, 11, 15 1 → 0 (11 is too large) 0 1 5

Why the result is always a value in the grid

In the third step of the walkthrough, mid was 6, a number that appears nowhere in the grid. The search tests such numbers all the time. So why can it not return one?

Suppose the loop ends at some x. Then countAtMost(x) is at least k, and countAtMost(x - 1) is less than k, because x is the first number to pass. The two counts differ, so at least one grid value is counted for x but not for x - 1. The only value that fits is x itself. A number missing from the grid, such as 6, always has the same count as the number before it, so it can never be the first to pass.

The same reasoning handles repeats. In the grid [[1, 2], [2, 3]] with k = 3, the counts for 1, 2 and 3 are 1, 3 and 4. The first count to reach 3 belongs to the value 2, which is the right answer: the sorted list is 1, 2, 2, 3.

Comparing the approaches

Approach Time Extra space Uses the sorted rows and columns
Flatten and sort O(n² log n) O(n²) No
Binary search on the value O(n log(max − min)) O(1) Yes, both

The binary search runs once per halving of the value range, which is log(max − min) times: about 31 rounds at most for 32-bit integers, however large the grid. Each round is one O(n) count. For a 1,000 by 1,000 grid that is roughly 31 × 2,000 = 62,000 cell reads, against sorting a million values.

The fast version is unusual in that its running time depends on the size of the numbers as well as the size of the grid. If the values were spread over an enormous range and the grid were tiny, sorting would be the better choice. A third well-known method keeps a min-heap holding one candidate from each row and removes the smallest k times, in O(k log n) time and O(n) space. It is a good fit when k is small, but for k near n² it is no better than sorting.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

const grid = [[1, 4, 9], [3, 7, 12], [8, 11, 15]];
console.log(kthSmallestInMatrix(grid, 5)); // 8
console.log(kthSmallestInMatrix(grid, 1)); // 1
console.log(kthSmallestInMatrix(grid, 9)); // 15
console.log(kthSmallestInMatrix([[1, 2], [2, 3]], 3)); // 2
console.log(countAtMost(grid, 8)); // 5

Python

grid = [[1, 4, 9], [3, 7, 12], [8, 11, 15]]
print(kth_smallest_in_matrix(grid, 5))  # 8
print(kth_smallest_in_matrix(grid, 1))  # 1
print(kth_smallest_in_matrix(grid, 9))  # 15
print(kth_smallest_in_matrix([[1, 2], [2, 3]], 3))  # 2
print(count_at_most(grid, 8))  # 5

The comment after each line is the result you should see.

Common mistakes

  • Binary searching over positions instead of values. There is no single sorted list of positions here. lo and hi are numbers that could be the answer, not row or column indices.
  • Counting values strictly less than mid. The test must be "less than or equal to". With a strict count, the search settles one above the true answer, which may not even be a number in the grid.
  • Returning as soon as the count equals k. A count of exactly k does not mean mid is in the grid. In the example with k = 3, countAtMost(6) is exactly 3, yet 6 is not in the grid; the answer is 4. Let the loop run until lo meets hi.
  • Writing hi = mid - 1. mid may be the answer when its count is at least k, so it has to stay in the range.
  • Resetting col for each row in the count. It still gives the right number, but every count becomes O(n²) and the whole method is slower than sorting.
  • Sorting numbers without a comparison function in JavaScript. values.sort() orders them as text. Always pass (a, b) => a - b.
  • Treating repeats as one value. Position k is counted with duplicates included.

Original problem: LeetCode 378: Kth Smallest Element in a Sorted Matrix