Window Peaks
HardSliding Window
Problem
A trading dashboard shows, for every block of k consecutive prices in nums, the highest price inside that block.
Return an array with the maximum of each window of length k, from left to right (there are nums.length - k + 1 of them).
Example 1
- Input:
- nums = [4, 2, 12, 3, 8, 1, 1], k = 3
- Output:
- [12, 12, 12, 8, 8]
Windows: [4,2,12], [2,12,3], [12,3,8], [3,8,1], [8,1,1].
Example 2
- Input:
- nums = [9], k = 1
- Output:
- [9]
Constraints
- 1 ≤ k ≤ nums.length ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
Hint
Show the first hint
A heap works in O(n log n). Can some elements be thrown away for good?
Walkthrough
How to approach it
01Clarify before coding
- How many outputs? n - k + 1, one per full window.
- Can values repeat or be negative? Yes to both.
- Is O(n log n) acceptable? It passes, but the expected answer is O(n).
02Brute force
For each window, scan its k elements for the maximum.
Cost: O(n·k) time: 2.5·10^9 steps for n = 10^5, k = 5·10^4. A max-heap with lazy deletion improves this to O(n log n).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.