Asked at

Kth Smallest Element In A Sorted Matrix

Hard
VerifiedBinary SearchMatrixHeap~35 min

Given an n × n matrix whose rows and columns are sorted ascending, return the kth smallest element in overall sorted order (counting duplicates).

Binary search on the value range: count how many entries are ≤ mid by walking from the bottom-left corner, then narrow the range. The input arrives as a single object { matrix, k }.

Examples

in{ matrix: [[1,5,9],[10,11,13],[12,13,15]], k: 8 }
out13

Sorted order is 1,5,9,10,11,12,13,13,15; the 8th value is 13.

in{ matrix: [[-5]], k: 1 }
out-5

The only element is the 1st smallest.

Constraints

  • n == matrix.length == matrix[i].length
  • 1 ≤ n ≤ 300
  • 1 ≤ k ≤ n²

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.