PreviousNext
Coding/Searching and sorting

Kth smallest in matrix

Write codeHard30 minGoogle and Amazon style

Your task

Given an n x n matrix where each row and each column is sorted in ascending order, return the k-th smallest element in the matrix (in overall sorted order). 1 <= n <= 300 and 1 <= k <= n*n. Aim to beat O(n^2 log n).

Examples

kth_smallest_matrix(matrix: list[list[int]], k: int) -> int
Example 1
Inputkth_smallest_matrix([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8)
Output13