The problem
A window of k values slides along the list a, one place at a time. Return the biggest value in each window, from the first window to the last. There are len(a) - k + 1 windows.
window_max([4, 2, 12, 3, 8, 5, 1, 7], 3)
# [12, 12, 12, 8, 8, 7]
window_max([5, 3, 8], 1) # [5, 3, 8]
Limits
- Up to 200,000 values.
kis at least 1 and at mostlen(a).kcan be large, so O(n × k) (n times k) is too slow.
Builds on STAQ-6 Monotonic queue.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
9 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The lesson's list | Not run | |
| 2 | k = 1 | Not run | |
| 3 | k = n | Not run | |
| 4 | Going down | Not run | |
| 5 | Going up | Not run | |
| 6 | Repeats | Not run | |
| 7 | Negative values | Not run | |
| 8 | 200,000 values, k = 50,000 | Not run | |
| 9 | 200,000 going down, k = 1,000 | Not run |