Every row and column in the library's shelving grid is sorted, and Arif wants to find the K-th smallest book ID across the entire grid without sorting everything from scratch. Given an N×N matrix where every row and every column is sorted ascending, and an integer K, find the K-th smallest element in the whole matrix. Solve using binary search on the VALUE (not the index), with a counting function, in better than O(N^2 log(N^2)) sorting time.
Input
Line1: N K. Next N lines: N integers each (row of the matrix).
Output
The K-th smallest value.
Constraints
1 ≤ N ≤ 300, 1 ≤ K ≤ N*N
Sample Input
3 5 1 5 9 10 11 13 12 13 15
Sample Output
11
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.