Sliding Window · 059Hard
Sliding Window Maximum
Given an array nums and a window size k, the window slides one position at a time from left to right. Return an array of the maximum in each window position.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
Examples
maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3) -> [3, 3, 5, 5, 6, 7] maxSlidingWindow([1], 1) -> [1] maxSlidingWindow([1, -1], 1) -> [1, -1] maxSlidingWindow([1,3,-1,-3,5,3,6,7], 8) -> [7] // k = n gives one value maxSlidingWindow([2, 2, 2, 2], 2) -> [2, 2, 2] // all same; n - k + 1 = 3 entries maxSlidingWindow([-7, -8, 7, 5, 7, 1, 6, 0], 4) -> [7, 7, 7, 7, 7] // negatives, and a tie between equal maxima
Edge cases
- k = 1 returns the array unchanged.
- k equal to the array length gives a single value.
- The result has exactly n - k + 1 entries.
Show the target complexity (spoiler)
- Naive
- O(n * k) time — rescan each window for its maximum. With n = 10^5 this times out.
- Target
- O(n) time, O(k) space — a monotonically decreasing deque of indices; the front is always the current window's maximum.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/03-sliding-window/059-sliding-window-maximum.js ./practice c 059