Show problems as
Classic problem #378MediumArrayBinary SearchSortingHeap (Priority Queue)Matrix

Kth Smallest Element in a Sorted Matrix

Real-world version: Kth Smallest Drift Reading
Tracked in this browser only
Read Kth Smallest Element in a Sorted Matrix on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstFinding Kth Largest/Smallest · Priority Queues, animated step by step

A calibration bench records the drift of a sensor at n oven temperatures and n supply voltages, giving a square table matrix of n rows and n columns. matrix[i][j] is the drift in micro-units, and it may be negative when the sensor reads low. Raising the temperature never lowers the drift and neither does raising the voltage, so every row of matrix reads left to right in non-decreasing order and every column reads top to bottom in non-decreasing order.

Given k, return the k-th smallest drift value in the table. Repeated values each take their own place in that ordering, so a table whose entries are all equal answers with that value for every k.

Aim for a routine that does not need room for all n * n readings at once.

Examples

Example 1

Input
matrix = [[2, 6, 8], [4, 7, 10], [9, 12, 14]], k = 5
Output
8

Listed in order the nine readings run 2, 4, 6, 7, 8, 9, 10, 12, 14. The fifth entry of that list is 8.

Example 2

Input
matrix = [[5, 5], [5, 9]], k = 3
Output
5

The four readings in order are 5, 5, 5, 9. The third of them is 5, because each repeat occupies its own place.

Example 3

Input
matrix = [[2, 5, 9], [3, 6, 10], [4, 7, 11]], k = 4
Output
5

In order the readings run 2, 3, 4, 5, 6, 7, 9, 10, 11, and the fourth is 5.

Constraints

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • Every row and every column of matrix is in non-decreasing order.
  • 1 <= k <= n^2

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def kth_smallest(matrix: list[list[int]], k: int) -> int:
Java
public int kthSmallest(int[][] matrix, int k)

More on the same topics