๐ Introduction
The sliding window maximum is a common problem in data structures and algorithms. It asks us to find the maximum value in every window of size k as we slide the window across an array. While the problem looks simple, solving it efficiently is very important in real-world applications like stock market analysis, signal processing, system monitoring, and competitive programming.
A naive solution takes O(nยทk) time, which becomes very slow when the input size is large. But with the right approach, we can solve this in O(n) linear time.
๐ What is the Sliding Window Maximum Problem?
Imagine you have an array of numbers, and you place a window of size k on it. The window covers k consecutive elements. As you slide the window from left to right, you want to know the maximum element in each window.
Example
Array = [1, 3, -1, -3, 5, 3, 6, 7], window size = 3
Windows and their maximums:
[1, 3, -1] โ max = 3
[3, -1, -3] โ max = 3
[-1, -3, 5] โ max = 5
[-3, 5, 3] โ max = 5
[5, 3, 6] โ max = 6
[3, 6, 7] โ max = 7
Final Output = [3, 3, 5, 5, 6, 7]
โก Naive Approach (Inefficient)
For each window of size k, scan all elements and find the maximum.
Time complexity = O(nยทk).
Problem: Very slow when n is large and k is also big.
๐ Best Approach: Using Deque (Double-Ended Queue)
The deque-based solution is the best way to solve the sliding window maximum problem in O(n) linear time. A deque is a data structure that allows insertion and deletion from both ends efficiently.
๐ก Key Idea
As we move the window, we maintain a deque that stores indices of array elements.
The deque is kept in decreasing order of values (front always holds the index of the maximum element).
For each step
Remove indices that are out of the current window.
Remove indices from the back if their values are smaller than the current element.
Add the current index to the deque.
The element at the front of the deque is the maximum for the current window.
๐ This way, each element is added and removed at most once โ Total O(n).
๐ฅ๏ธ Python Implementation
from collections import deque
def sliding_window_max(nums, k):
dq = deque()
result = []
for i in range(len(nums)):
# 1. Remove indices outside the current window
while dq and dq[0] <= i - k:
dq.popleft()
# 2. Remove smaller elements from the back
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
# 3. Add current element's index
dq.append(i)
# 4. Record the maximum for windows of size k
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Example
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(sliding_window_max(nums, k)) # Output: [3, 3, 5, 5, 6, 7]
๐ Why Deque Works Efficiently
Each element is processed once โ added and removed from deque only once.
Deque always stores useful candidates โ smaller elements that canโt be maximum are removed quickly.
Maximum is always at the front โ constant-time access for every window.
Thus, total time complexity = O(n).
๐ Real-World Applications
๐ Stock Prices: Find the highest stock price in the last k days.
๐ก Signal Processing: Track maximum signal strength in a moving window.
๐ฅ๏ธ System Monitoring: Detect maximum CPU/memory usage in recent intervals.
๐ฎ Gaming: Calculate maximum scores over rolling time windows.
โ
Summary
The best way to solve the sliding window maximum problem in linear time is by using a deque (double-ended queue). This method ensures:
Each element is processed at most once.
Maximums are found in O(1) per window.
Total runtime is O(n), making it much faster than the naive O(nยทk) method.
This algorithm is widely used in stock market analysis, monitoring systems, gaming, and competitive programming. By mastering the deque-based approach, you can handle large datasets efficiently and build high-performance solutions.