Loading...
Loading...
Loading...
A coaching institute prints its fee chart as an n × n table. Fees rise from left to right along every row, and from top to bottom down every column. Equal fees are allowed.
A student wants the k-th smallest fee in the whole table: put all n × n fees in one list, sort it from low to high, and take the fee at position k. Equal fees count as separate entries.
Example 1
Input
3 8 1 5 9 10 11 13 12 13 15
Output
13
Sorted, the fees are 1 5 9 10 11 12 13 13 15. Position 8 holds the second 13.
Example 2
Input
2 2 1 2 1 3
Output
1
Sorted: 1 1 2 3. The 1 at the start of row 2 comes before the 2 in row 1.
Try the problem first. Open one hint at a time.
Each row is a sorted list. Finding the k-th smallest is like merging n sorted lists and stopping after k values.
Start a min-heap with the first fee of every row, remembering its row and column.
Remove the smallest entry. Then add the fee just to its right in the same row, if there is one.
The k-th entry you remove is the answer.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor