Description
Given an n x n matrix where each row and column is sorted in ascending order, return the kth smallest element.
Examples
Input:
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8Output:
13Explanation:
Sorted elements: 1,5,9,10,11,12,13,13,15. The 8th smallest is 13. Use binary search or min-heap.
Input:
matrix = [[-5]], k = 1Output:
-5Explanation:
A 1x1 matrix has only one element. The 1st smallest is -5.
Input:
matrix = [[2,4,6,8],[3,5,7,9],[10,12,14,16],[11,13,15,17]], k = 5Output:
6Explanation:
In this 4×4 matrix, the elements in sorted order are: 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17. The 5th smallest element is 6.
Constraints
- •
1 ≤ n ≤ 300