How to Solve Sliding Window Maximum on LeetCode
The Sliding Window Maximum is a classic LeetCode problem that tests your grasp of window-based algorithms, efficient data structures, and optimization.
Problem Statement
Given an array nums and an integer k, there is a sliding window of size k which moves from the very left to the very right. You can only see the k numbers in the window. Return the max sliding window.
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Why This Problem Matters for Interviews
This problem:
- Checks your mastery of deques and monotonic queues
- Requires optimal use of data structures to reduce time complexity
- Is a common pattern for processing subarrays efficiently
Approaches to Sliding Window Maximum
1. Deque (Monotonic Queue, Optimal)
Store indices, remove from deque if out of window or less than current number.
Time Complexity: O(n)
Space Complexity: O(k)
from collections import deque
def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
q, res = deque(), []
for i, n in enumerate(nums):
while q and q[0] <= i - k:
q.popleft()
while q and nums[q[-1]] < n:
q.pop()
q.append(i)
if i >= k - 1:
res.append(nums[q[0]])
return res
2. Max Heap (Suboptimal)
Push into max-heap, pop out-of-window elements.
Time Complexity: O(n log k)
Space Complexity: O(k)
import heapq
def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
res, heap = [], []
for i in range(len(nums)):
heapq.heappush(heap, (-nums[i], i))
if i >= k - 1:
while heap[0][1] <= i - k:
heapq.heappop(heap)
res.append(-heap[0][0])
return res
Key Interview Talking Points
- Why naive solution (O(nk)) is too slow
- Monotonic queue idea and deque implementation
- When to use heaps vs deques
- Handling edge cases (empty input, k=1)
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Deque | O(n) | O(k) |
| Max Heap | O(n log k) | O(k) |
Pro Interview Tips
- Walk through the window’s movement on sample input.
- Explain popping from deque and heap in context.
- Practice with test cases