Kth Smallest Element in a Sorted Matrix

1. Define the problem

Kth Smallest Element in a Sorted Matrix

You are given an n x n matrix where every row and every column is sorted in ascending order. Return the kth smallest element in the matrix. Seed a min-heap with the first element of every row. Each time you pop the smallest, push the next element in that same row — the row and column ordering guarantees it is a valid next candidate.

Constraints

n == matrix.length == matrix_i.length
1 ≤ n ≤ 300
-10⁹ ≤ matrix_i[j] ≤ 10⁹
All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order
1 ≤ k ≤ n^2

Example

Inputmatrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8

Output13

Explanation Sorted, the matrix values are 1, 5, 9, 10, 11, 12, 13, 13, 15 — the 8th is 13.

2. Visualize the solution

Seed one entry per row, pop k times

slot 01

slot 110

slot 212

Statusseed

Heap seeded with the first column. Heap array: 1, 10, 12.

What happens in this step

push [1, row0, col0], [10, row1, col0], [12, row2, col0]
heap (array) = [[1,0,0], [10,1,0], [12,2,0]]

Each row contributes its smallest (leftmost) value. 1 is already less than both 10 and 12, so no sift-up swaps are needed — 1 sits at the root.

Step 1 of 4

Steps to visualize

Push the first element of every row into a min-heap, tagged with its row and column.
The row is the heap array: three slots. A slot marked — is empty.
Pop the smallest value — that is the next smallest overall.
Push the next element from the same row, if one exists.
After k pops, the last popped value is the answer.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Seed one entry per row, pop k times

slot 01

slot 110

slot 212

Statusseed

Heap seeded with the first column. Heap array: 1, 10, 12.

What happens in this step

push [1, row0, col0], [10, row1, col0], [12, row2, col0]
heap (array) = [[1,0,0], [10,1,0], [12,2,0]]

Each row contributes its smallest (leftmost) value. 1 is already less than both 10 and 12, so no sift-up swaps are needed — 1 sits at the root.

Step 1 of 4

4. Solution

Solution

solution.tsTypeScript

function kthSmallest(matrix, k) {
  const n = matrix.length;
  const heap = []; // entries stored as [value, row, col]

  function push(item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent][0] > heap[i][0]) {
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
      } else {
        break;
      }
    }
  }

  function siftDown() {
    let i = 0;
    const size = heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < size && heap[left][0] < heap[smallest][0]) smallest = left;
      if (right < size && heap[right][0] < heap[smallest][0]) smallest = right;
      if (smallest === i) break;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
  }

  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      siftDown();
    }
    return top;
  }

  for (let row = 0; row < n; row++) {
    push([matrix[row][0], row, 0]);
  }

  let result = 0;
  for (let i = 0; i < k; i++) {
    const [value, row, col] = pop();
    result = value;
    if (col + 1 < matrix[row].length) {
      push([matrix[row][col + 1], row, col + 1]);
    }
  }

  return result;
}

Time: O(k log n)
Space: O(n)

5. Test cases

Test cases

Input	Expected	Covers
`matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8`	`13`	example from the docstring
`matrix = [[1, 2], [1, 3]], k = 1`	`1`	k = 1 returns the overall smallest value
`matrix = [[1, 2], [3, 4]], k = 4`	`4`	k equals n squared, returns the overall largest value
`matrix = [[1, 2, 3, 4, 5]], k = 3`	`3`	a 1xN matrix, degenerates to a plain sorted array
`matrix = [[7]], k = 1`	`7`	smallest valid input, a 1x1 matrix
`matrix = [[1, 1, 3], [1, 2, 3], [2, 3, 3]], k = 5`	`2`	repeated values across rows and columns
`matrix = [[1, 3], [2, 4]], k = 2`	`2`	a compact 2x2 matrix

Kth Smallest Element in a Sorted Matrix