Loading...
Loading...
Loading...
Farhan is a food-delivery rider. His app shows a typical delivery time: the median of his last k delivery times, in minutes.
The median of k values is the value in place (k + 1) / 2 (rounded down) when they are sorted in ascending order. So for k = 3 it is the middle value, and for k = 4 it is the second smallest.
Given all n delivery times in order, print the median of every block of k consecutive times, from the first block to the last. The values can be negative because the app stores them as the difference from a target time.
Example 1
Input
8 3 1 3 -1 -3 5 3 6 7
Output
1 -1 -1 3 5 6
The first block 1, 3, −1 sorted is −1, 1, 3, so its median is 1.
Example 2
Input
5 2 1 3 2 2 6
Output
1 2 2 2
For k = 2 the median is the smaller of the two values.
Try the problem first. Open one hint at a time.
Sorting every block from scratch costs O(k log k) per block, which is too slow when n and k are both large.
Split each block into a lower half and an upper half, with the lower half one bigger when k is odd. The median is then the largest value of the lower half.
When the block slides, one value leaves and one joins. Remove it from its half, add the new one to the right half, and move one value across if the sizes are off.
Keep the two halves in two TreeSets of indexes ordered by (value, index). Unlike PriorityQueue, a TreeSet removes any value in O(log k) and keeps repeated values apart.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor