K-th Smallest in a Sorted Grid

MediumBinary Search

Problem

You are given an n × n grid in which every row and every column is sorted in non-decreasing order, and an integer k.

Return the k-th smallest value among all n² cells, counting duplicates separately. Try to use less than O(n²) extra memory.

Example 1

Input:
grid = [[1, 3, 7], [2, 6, 8], [5, 9, 12]], k = 5
Output:
6

Sorted, the cells are 1, 2, 3, 5, 6, 7, 8, 9, 12; the 5th is 6.

Example 2

Input:
grid = [[-3, 0], [1, 4]], k = 2
Output:
0

Example 3

Input:
grid = [[7]], k = 1
Output:
7

Constraints

  • 1 ≤ n ≤ 300
  • -10^9 ≤ grid[i][j] ≤ 10^9
  • Rows and columns are non-decreasing.
  • 1 ≤ k ≤ n²

Hint

Show the first hint

Rather than searching for a position, search for the value: for a candidate x, how many cells are ≤ x?

Walkthrough

How to approach it

01Clarify before coding

  • Do duplicates count separately? Yes, the k-th entry of the fully sorted list.
  • Is the grid square? Yes, n × n.
  • Are values bounded? Yes, ±10^9, so a value-range binary search takes about 31 steps.

02Brute force

Copy all cells into a list, sort, return index k - 1. A min-heap seeded with the first column and popped k times is the usual improvement.

Cost: Sorting: O(n² log n) time, O(n²) memory. Heap: O(k log n) time, O(n) memory, up to 9 · 10^4 · 9 pops.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.