The Sliding Window Maximum Problem
I've tackled countless problems involving arrays, sliding windows, and dynamic programming.
One such classic problem is the Sliding Window Maximum, which frequently appears in coding interviews and real-world applications like data stream analysis.
In this article, I'll walk you through two solutions to this problem:
1) A non-optimal brute-force approach
2) An optimized solution using a monotonic deque.
By the end, you'll understand the key differences between the two and how to implement the most efficient solution.
Understanding the Problem
The Sliding Window Maximum problem requires us to find the maximum value in every contiguous subarray (window) whose size is `k` in a given array `nums`.
For example:
#Input
`nums = [1, 2, 1, 0, 4, 2, 6]`, `k = 3`
# Output:
`[2, 2, 4, 4, 6]`
This problem tests your ability to balance time and space efficiency, making it a favorite among interviewers.
Non-Optimal Solution: Brute Force with Max-Heap
Let's start with a straightforward but inefficient approach using a max-heap. Here's the code:
from typing import List
import heapq
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
"""
Finds the maximum value in each sliding window of size k using a max-heap.
Args:
nums (List[int]): The input array.
k (int): The size of the sliding window.
Returns:
List[int]: A list of maximum values for each window.
"""
res = [] # To store the result
for r in range(len(nums) - k + 1):
win = nums[r:r + k] # Extract the current window
max_heap = [] # Initialize a max-heap
# Push all elements into the heap
for i in win:
heapq.heappush(max_heap, -1 * i) # Use negative values for max-heap
val = heapq.heappop(max_heap) # Pop the largest element
res.append(-1 * val) # Append the maximum value to the result
return res
How It Works
1. For each window of size `k`, extract the subarray.
2. Use a max-heap (simulated with a min-heap and negative values) to find the maximum value in the window.
3. Append the maximum value to the result list.
Time and Space Complexity
- Time Complexity: O(nlog k)
- We iterate through `n - k + 1` windows, and for each window, building the heap takes O(k log k).
- Space Complexity: O(n + k)
- The result list takes O(n) space, and the heap uses O(k) space.
Why It's Inefficient
The brute-force approach recalculates the maximum for every window from scratch, leading to redundant computations.
Optimized Solution: Monotonic Deque
To improve efficiency, we use a monotonic deque (double-ended queue). This approach ensures that we process each element only once, achieving linear time complexity. Here's the optimized code:
from typing import List
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
"""
Finds the maximum value in each sliding window of size k using a monotonic deque.
Args:
nums (List[int]): The input array.
k (int): The size of the sliding window.
Returns:
List[int]: A list of maximum values for each window.
"""
if not nums or k == 0:
return []
res = [] # To store the result
dq = deque() # Deque to store indices of elements in the current window
for i, num in enumerate(nums): # Iterate through the array
# Remove indices of elements that are out of the current window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove indices of elements smaller than the current element
while dq and nums[dq[-1]] < num:
dq.pop()
# Add the current element's index to the deque
dq.append(i)
# If the window has reached size k, append the maximum to the result
if i >= k - 1:
res.append(nums[dq[0]])
return res
How It Works
1. Use a deque to store indices of elements in the current window.
2. Maintain the deque in decreasing order of values:
- Remove indices of elements that are out of the current window.
- Remove indices of elements smaller than the current element.
3. The maximum value in the current window is always at the front of the deque.
Time and Space Complexity
Time Complexity: O(n)
Each element is processed at most twice (added and removed from the deque).
Space Complexity: O(k)
The deque stores at most `k` indices.
Why It's Efficient
The deque ensures that we only process each element once, eliminating redundant calculations.
Key Differences Between the Two Solutions
Aspect Brute Force with Max-Heap Optimized with Monotonic Deque
Time Complexity O(n * k log k)) O(n)
Space Complexity O(n + k) O(k)
Approach recalculates max for each window processes each element once
Efficiency inefficient for large inputs highly efficient |
Why the Optimized Solution Works Better
The optimized solution leverages the monotonic deque to maintain a dynamic window of candidates for the maximum value.
It guarantees that the maximum value is always accessible in constant time. This is through removing unnecessary elements and keeping the deque in decreasing order.
This approach is the preferred solution for this problem. Because it is not just elegant, it is also efficient.
Alternative: Optimized Solution
from typing import List
import heapq
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# Max heap, but use negative values to simulate it with `heapq`
max_heap = []
res = []
for i in range(len(nums)):
#Push the current value along with its index into the heap(negative for max-heap behavior)
heapq.heappush(max_heap, (-nums[i], i))
# Remove elements not in the current window
while max_heap[0][1] <= i - k:
heapq.heappop(max_heap)
# Only add to the result once the first window is fully traversed
if i >= k - 1:
res.append(-max_heap[0][0]) # The largest value in the current window
return res
# Testing the solution
sol = Solution()
nums = [1, 2, 1, 0, 4, 2, 6]
print(sol.maxSlidingWindow(nums, 3))
Explanation
Heap Storage: Each entry in the heap is stored as a tuple (-nums[i], i), where -nums[i] ensures max-heap behavior.
Heap Cleanup: Remove elements from the heap that fall outside the sliding window (i - k).
Efficient Updates: By maintaining the heap dynamically as the window slides, the solution achieves O(n) time complexity, as each element is pushed and popped from the heap at most once.
# Output: For the input nums = [1, 2, 1, 0, 4, 2, 6] and k = 3, the output will be:
[2, 2, 4, 4, 6]
What You Should Do Next
Now that you understand both the brute-force and optimized solutions try implementing them yourself!
Test the code with different inputs and see how they differ in performance!
Practice similar sliding window problems to strengthen your problem-solving skills.
By mastering these techniques, you'll not only ace coding interviews but also develop a deeper understanding of algorithmic efficiency.
Happy coding!