Modified Binary Search
LC #378Medium
Kth Smallest Element in a Sorted Matrix
Modified Binary Search
GoogleAmazonAppleBloombergProblem
Find the kth smallest element in an n×n matrix where each row and column is sorted.
binary-searchmatrixheap
Constraints
- ›n == matrix.length == matrix[i].length
- ›1 ≤ n ≤ 300
- ›-2³¹ ≤ matrix[i][j] ≤ 2³¹-1
- ›1 ≤ k ≤ n²
Example
Input
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8Output
13Why
Sorted: [1,5,9,10,11,12,13,13,15]. 8th element = 13.