The best of the window minimums
Reported in interviews at (where)
You are given a list of n whole numbers and a window length k. Slide a window of k numbers side by side along the list, from the start to the end, and note the smallest number in each window.
For each test, print the largest of those smallest numbers.
Finding the smallest of each window from scratch costs O(n k), too slow for the largest tests. Aim for O(n).
Input
The first line holds T, the number of tests. Each test is two lines: n and k, then the n whole numbers of the list.
Output
For each test, one line: the largest of its window minimums.
- Input
3
6 3
2 5 4 6 8 1
3 3
7 1 9
4 1
-3 -8 -1 -5- Output
4
1
-1
- The windows are 2 5 4, 5 4 6, 4 6 8 and 6 8 1, with smallest numbers 2, 4, 4 and 1. The largest of those is 4.
- One window covers the whole list.
- With k = 1 each number is its own window: the answer is the largest number.
Limits
1 <= T <= 1001 <= k <= n <= 100000the n of all the tests add up to at most 400000-1000000000 <= each number <= 1000000000
Hints
Hint 1
Keep the positions of the window's candidates for its minimum in a double-ended queue, their numbers rising from front to back.
Hint 2
Before adding a number, drop from the back every number not smaller than it: they can never be a minimum again. Drop the front when it leaves the window. The front is always the window's minimum.
Where this was reported
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.