Description
Given an n x n matrix where each row and column is sorted in ascending order, return the kth smallest element in the matrix.
Examples
Input:
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8Output:
13Explanation:
Elements in sorted order: 1,5,9,10,11,12,13,13,15. 8th is 13.
Input:
matrix = [[-5]], k = 1Output:
-5Explanation:
Works with negative numbers.
Input:
matrix = [[1,3,5,7],[2,4,6,8],[9,10,11,12],[13,14,15,16]], k = 6Output:
6Explanation:
Flattening and sorting: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16. The 6th smallest is 6. Notice elements interleave between rows (e.g., row 2 starts with 2 which is smaller than row 1's later elements), requiring a min-heap or binary search approach rather than simple row-by-row traversal.
Constraints
- •
n == matrix.length == matrix[i].length - •
1 ≤ n ≤ 300 - •
1 ≤ k ≤ n²