239. Sliding Window Maximum
- Array
- Sliding Window
- Heap (Priority Queue)
TIME
O(n)
SPACE
O(k)
Intuition
A heap gives O(n log n), but most of what it stores is useless. If a new element b arrives and an older element a in the window has a <= b, then a can never be a maximum again: b is at least as large and stays in the window longer. So only elements with nothing as large to their right matter. Those form a strictly decreasing sequence, and its first element is the window's maximum.
Approach
Keep a deque of indices whose values strictly decrease from front to back. For each index i:
- Pop the front if it has left the window, meaning it equals
i - k. - Pop from the back while
nums[back] <= nums[i]. - Push
ion the back. - Once
i >= k - 1, recordnums[front].
Complexity
- Time: O(n), since each index is pushed once and popped at most once
- Space: O(k) for the deque, plus the output
Edge Cases
k == 1: every element is its own window, and the deque never holds more than one indexk == n: a single window, so the output has one value- Duplicates: popping on
<=keeps the newer copy, which stays in the window longer - Increasing input: each new element clears the deque
- Decreasing input: the deque fills to
kand only the front expiry removes elements
Code
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
"""
239. Sliding Window Maximum
Time: O(n)
Space: O(k)
"""
# Indices whose values strictly decrease from front to back. The front
# is the current maximum.
dq = deque()
out = []
for i, x in enumerate(nums):
if dq and dq[0] == i - k:
dq.popleft()
# An older value <= x can never be a maximum again.
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if i >= k - 1:
out.append(nums[dq[0]])
return out/**
* 239. Sliding Window Maximum
* Time: O(n)
* Space: O(k)
*/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
// Circular deque of indices whose values strictly decrease from front
// to back. It holds at most k + 1 indices. The front is the current maximum.
int cap = k + 1;
int[] dq = new int[cap];
int head = 0, size = 0;
int[] out = new int[n - k + 1];
for (int i = 0; i < n; i++) {
if (size > 0 && dq[head] == i - k) {
head = (head + 1) % cap;
size--;
}
// An older value <= nums[i] can never be a maximum again.
while (size > 0 && nums[dq[(head + size - 1) % cap]] <= nums[i]) {
size--;
}
dq[(head + size) % cap] = i;
size++;
if (i >= k - 1) {
out[i - k + 1] = nums[dq[head]];
}
}
return out;
}
}