All problems

Kth Smallest Element in a Sorted Matrix

Medium · heap

You are given matrix, a square grid of integers with n rows and n columns. Every row is sorted from left to right in non-decreasing order, and every column is sorted from top to bottom in non-decreasing order.

Imagine writing out all n * n numbers of the grid in one list from smallest to largest. Return the number in position k of that list, counting from 1.

Equal numbers each take their own position. For example, in the sorted list 2, 2, 5 the 2nd number is 2, not 5.

Examples

Example 1

Input: matrix = [[1, 4, 7], [2, 5, 9], [3, 6, 10]], k = 5

Output: 5

Written in order the numbers are 1, 2, 3, 4, 5, 6, 7, 9, 10, so the 5th is 5.

Example 2

Input: matrix = [[2, 3], [3, 8]], k = 3

Output: 3

The numbers in order are 2, 3, 3, 8. The two 3s take positions 2 and 3.

Example 3

Input: matrix = [[-4]], k = 1

Output: -4

A single number is its own first number.

Constraints

• n == len(matrix) == len(matrix[0])
• 1 <= n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• Every row and every column is sorted in non-decreasing order
• 1 <= k <= n * n