Problem Statement
Given an array nums and an integer k, return the maximum element for every sliding window of size k.
Brute Force Intuition
In an interview, you can explain it like this:
For every window of size
k, iterate through all its elements and find the maximum.
Since every window is scanned completely, many elements are processed repeatedly.
Complexity
- Time Complexity: O(N × K)
- Space Complexity: O(1)
Brute Force Code
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n - k + 1];
int index = 0;
for (int i = 0; i <= n - k; i++) {
int max = nums[i];
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
ans[index++] = max;
}
return ans;
}
}
Moving Towards the Optimal Approach
Notice that while moving the window:
One element leaves
One element enters
Do we really need to calculate the maximum again?
No.
We only need to keep the useful candidates that can become the maximum.
This is where a Monotonic Deque comes in.
Pattern Recognition
Whenever you see:
- Sliding Window
- Maximum / Minimum in every window
- Fixed Window Size
Think:
Monotonic Deque
Key Observation
Maintain indices in a deque such that:
Elements remain in decreasing order.
Then:
Front of deque
=
Maximum of current window
Whenever a new element comes:
Remove all smaller elements from the back.
They can never become the maximum.
Optimal Approach
For every index:
Step 1
Remove indices outside the window.
deque.peekFirst() <= i - k
Step 2
Remove smaller elements from the back.
nums[deque.peekLast()] <= nums[i]
Step 3
Insert current index.
Step 4
Once window size becomes k:
Front of deque
=
Maximum
Optimal Java Solution
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>();
int index = 0;
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() &&
dq.peekFirst() <= i - k) {
dq.pollFirst();
}
while (!dq.isEmpty() &&
nums[dq.peekLast()] <= nums[i]) {
dq.pollLast();
}
dq.offerLast(i);
if (i >= k - 1) {
ans[index++] = nums[dq.peekFirst()];
}
}
return ans;
}
}
Dry Run
Input
nums = [1,3,-1,-3,5,3,6,7]
k = 3
Window
[1 3 -1]
Deque:
3
Maximum:
3
Window
[3 -1 -3]
Maximum:
3
Window
[-1 -3 5]
Remove:
-3
-1
Deque:
5
Maximum:
5
Continue similarly.
Final Answer:
[3,3,5,5,6,7]
Why Monotonic Deque Works?
Every index:
Inserted once
Removed once
So each element is processed only one time.
The deque always maintains candidates in decreasing order.
The front always stores the maximum element of the current window.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(K) |
Interview One-Liner
Maintain a monotonic decreasing deque of indices so the front always represents the maximum element of the current sliding window.
Pattern Learned
Sliding Window
+
Maximum / Minimum
↓
Monotonic Deque
Similar Problems
- Sliding Window Maximum
- Sliding Window Minimum
- First Negative Integer in Every Window
- Shortest Subarray with Sum at Least K
- Constrained Subsequence Sum
Memory Trick
Think:
New Element Arrives
↓
Remove Smaller Elements
↓
Insert Current Index
↓
Front = Maximum
Mental Model
Sliding Window
↓
Useful Candidates Only
↓
Deque
↓
Front Always Maximum
Whenever you hear:
"Maximum in every sliding window"
your brain should immediately think:
Monotonic Deque