Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumquick-select

Kth Smallest Element in a Sorted Matrix

Problem (restated)

An n × n matrix with each row and each column sorted ascending. Return the kth smallest value (1-indexed). Duplicates count separately.

Intuition

Flattening and quick-selecting works but throws away the sorted structure. Better: a min-heap of the n row heads, pop k times (each pop pushes the next cell in that row). Or binary-search the value range and count how many entries are ≤ mid by walking from the top-right.

Approaches

Min-heap of row heads

Unverified

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

Idea. Push (matrix[r][0], r, 0) for every row. Pop the global min k times; after popping (v, r, c) push (matrix[r][c+1], r, c+1) if it exists. The kth pop is the answer.

Walkthrough. [[1,5,9],[10,11,13],[12,13,15]], k=8. After eight pops you land on 13.

Trade-offs. Uses the row-sorted property. k can be n², so O(n² log n) worst. Quick select on a flattened copy is average O(n²) and ignores columns.

Solution

/** Toy min-heap: sort + shift. Interview/production: binary heap. */
export function kthSmallest(matrix: number[][], k: number): number {
  const n = matrix.length;
  const pq: [number, number, number][] = [];
  for (let r = 0; r < n; r++) pq.push([matrix[r]![0]!, r, 0]);
  let v = 0;
  for (let t = 0; t < k; t++) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const cur = pq.shift()!;
    v = cur[0]!;
    const r = cur[1]!, c = cur[2]!;
    if (c + 1 < n) pq.push([matrix[r]![c + 1]!, r, c + 1]);
  }
  return v;
}

/** Toy min-heap: sort + shift. Interview/production: binary heap. */
export function kthSmallest(matrix: number[][], k: number): number {
  const n = matrix.length;
  const pq: [number, number, number][] = [];
  for (let r = 0; r < n; r++) pq.push([matrix[r]![0]!, r, 0]);
  let v = 0;
  for (let t = 0; t < k; t++) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const cur = pq.shift()!;
    v = cur[0]!;
    const r = cur[1]!, c = cur[2]!;
    if (c + 1 < n) pq.push([matrix[r]![c + 1]!, r, c + 1]);
  }
  return v;
}

Binary search on value

Unverified

Time O(n log n log Δ)Space O(1)

Idea. Search lo = matrix[0][0], hi = matrix[n-1][n-1]. Count ≤ mid in O(n): start each row from the right and walk left. If the count is < k, go right; else go left. lo converges to the kth value.

Walkthrough. Same matrix, k=8. Values in [1,15]; the smallest candidate with at least 8 entries ≤ it is 13.

Trade-offs. No extra heap. Count must be O(n), not O(n²). This is binary-search-on-answer applied to an order statistic.

Solution

export function kthSmallest(matrix: number[][], k: number): number {
  const n = matrix.length;
  const countLe = (x: number): number => {
    let c = 0, j = n - 1;
    for (let i = 0; i < n; i++) {
      while (j >= 0 && matrix[i]![j]! > x) j--;
      c += j + 1;
    }
    return c;
  };
  let lo = matrix[0]![0]!, hi = matrix[n - 1]![n - 1]!;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (countLe(mid) < k) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

export function kthSmallest(matrix: number[][], k: number): number {
  const n = matrix.length;
  const countLe = (x: number): number => {
    let c = 0, j = n - 1;
    for (let i = 0; i < n; i++) {
      while (j >= 0 && matrix[i]![j]! > x) j--;
      c += j + 1;
    }
    return c;
  };
  let lo = matrix[0]![0]!, hi = matrix[n - 1]![n - 1]!;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (countLe(mid) < k) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Template connection

Kth-smallest selection on a structured source. Heap / binary search beat flattening + quick select because rows and columns are sorted.

Reflection

Heap: push each row’s head. After a pop, push the next cell in that row. The kth pop is the answer.
Binary search on the value. Because each row is sorted, counting entries <= mid is O(n). A count below k moves right.
k = 1 is the smallest and k = n * n is the largest. Duplicates count as separate entries. A negative search range is fine.