Mid-levelMid (3–6 yrs)CodingPythonGoogleMetaUber
Sliding window maximum
Explain the deque approach for Sliding Window Maximum. Why is it O(n)?
Answers use simple, clear English.
Audio N/ATime: O(n)Space: O(k)
Quick interview answer
Maintain a monotonic decreasing deque of indices. Pop back while nums[back] <= current; pop front if out of window. Front is always max.
Detailed answer
Maintain a monotonic decreasing deque of indices. Pop back while nums[back] <= current; pop front if out of window. Front is always max. Each index enters/leaves deque once → O(n). Prefer this over heap O(n log n) for fixed window max.
Real example & use case
Realtime metrics: max latency in last 60 samples.
Pros & cons
Pros: linear time. Cons: trickier to code under pressure.
Code example
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
dq: deque[int] = deque()
out: list[int] = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
if i >= k - 1:
out.append(nums[dq[0]])
return outPractice code · python (view only · no execution)
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
dq: deque[int] = deque()
out: list[int] = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
if i >= k - 1:
out.append(nums[dq[0]])
return out#dsa#sliding-window#deque