Loading...
Loading...
Loading...
An n by n grid has every row sorted ascending and every column sorted ascending. Print the k-th smallest value in the whole grid, counting repeated values separately.
Example
Input
3 8 1 5 9 10 11 13 12 13 15
Output
13
Try the problem first. Open one hint at a time.
Binary search the value, not a position. For a value x, count how many grid values are at most x.
Count with a staircase walk: for each row, move the column pointer left while the cell is above x. The first value x whose count is at least k is the answer.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor