Loading...
Loading...
Loading...
The exam cell stacks answer sheets by roll number, but the stack got slightly shuffled on the way. No sheet moved far: every value is at most k places away from where it belongs in sorted order.
You get the n numbers in their current order and the value k. Print them in ascending order. Try to use the fact that k can be much smaller than n.
Example 1
Input
7 3 6 5 3 2 8 10 9
Output
2 3 5 6 8 9 10
The smallest value 2 is 3 places from the front, which is allowed for k = 3.
Example 2
Input
6 1 2 1 4 3 6 5
Output
1 2 3 4 5 6
With k = 1, neighbours can only swap.
Try the problem first. Open one hint at a time.
The smallest value must be among the first k + 1 values. Why?
After you print it, the next smallest is among the remaining values of that window plus the next new value.
Keep a group of at most k + 1 candidates. Each step adds one new value and takes out the smallest.
Use a min-heap (PriorityQueue) of size k + 1. When the input runs out, empty the heap in order.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor