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:
8th smallest is 13.
Input:
matrix = [[-5]], k = 1Output:
-5Explanation:
Works with negative numbers.
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