Given an n x n matrix where every row and every column is sorted in ascending order, return the kth smallest element in the matrix. Ranking is over all n^2 entries, so duplicates count multiple times.
Input
matrix: n x n grid of integers, sorted along rows and columns
k: 1-indexed rank of the desired element
Output
The kth smallest value in the matrix.
Examples
Example 1
Inputmatrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Output13
Example 2
Inputmatrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k = 3
Output3
Constraints
1 <= n <= 1000
1 <= k <= n^2