Loading...
Loading...
Loading...
A n by n table of integers has every row sorted from left to right and every column sorted from top to bottom. Print the k-th smallest value in the whole table. Equal values count separately.
Example 1
Input
3 8 1 5 9 10 11 13 12 13 15
Output
13
Sorted: 1 5 9 10 11 12 13 13 15. The 8th is 13.
Example 2
Input
1 1 7
Output
7
Try the problem first. Open one hint at a time.
The smallest value is at the top-left corner. After taking a value, the next candidates are the cell below and the cell to the right.
Keep a heap of (value, row, column), starting with the first column of every row.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor