K-th Smallest in a Sorted Matrix
mediumMatrix+20 XPTime limit 2s
In an n × n matrix every row and every column is sorted in non-decreasing order. Find the k-th smallest value among all n² cells (counting repeated values separately: in 1 1 2 the 2nd smallest is 1).
Input:
- line 1:
n k - next
nlines:nintegers each
Output: the k-th smallest value.
Constraints: 1 ≤ n ≤ 300, 1 ≤ k ≤ n², −10⁹ ≤ value ≤ 10⁹.
Think about it: binary search on the answer value, not on positions. For a guess mid, count how many cells are ≤ mid with a staircase walk (start at the top-right of the matrix, O(n) per count). The smallest mid whose count is at least k is the answer. A min-heap that pops k times also works.
Sample input 1
3 8 1 5 9 10 11 13 12 13 15
Sample output 1
13
Sample input 2
2 2 1 2 1 3
Sample output 2
1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).