Introduction

The Sliding Window Maximum problem involves finding the maximum element in every window of size k.

Given:

an array
window size k

the task is to:

return maximum element
from every sliding window

This problem is one of the most important applications of:

 Monotonic Deque

This problem helps in understanding:

sliding window technique
deque operations
monotonic structures
efficient range queries

Example

Input:arr = [1,3,-1,-3,5,3,6,7]
k = 3

Output:
[3,3,5,5,6,7]

Explanation:
Window 1:
[1,3,-1]
Maximum:
3

Window 2:
[3,-1,-3]
Maximum:
3

Constraints

1 <= arr.length <= 10^5-10^4 <= arr[i] <= 10^4
1 <= k <= arr.length

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

Traverse every window
Find maximum element
inside current window
Store result

This works but repeated scanning increases complexity.

Steps

Traverse all windows.
Scan current window.
Find maximum value.
Store result.
Return answer array.

Dry Run

Input:[1,3,-1,-3,5,3,6,7]
k = 3

Window:
[1,3,-1]
Maximum:
3

Window:
[3,-1,-3]
Maximum:
3

Window:
[-1,-3,5]
Maximum:
5

Final Result:
[3,3,5,5,6,7]

Brute Force Code

Complexity Analysis

Time Complexity: O(n * k)Explanation:
Each window is scanned completely.

Space Complexity: O(1)
Explanation:
Only result storage is used.

Approach 2 : Monotonic Deque

Explanation

The optimized solution uses:

 Monotonic Decreasing Deque

Deque stores:

indices of useful elements

Rules:

Remove smaller elements
from back
Remove out-of-window indices
from front
Front always stores maximum

This gives:

O(n) solution

Steps

Create deque.
Remove smaller elements.
Remove expired indices.
Insert current index.
Store front element as maximum.

Dry Run

Input:[1,3,-1,-3,5,3,6,7]
k = 3

Process 1:
Deque:
[1]

Process 3:
Remove 1
Deque:
[3]

Process -1:
Deque:
[3,-1]

Window complete

Maximum:
3

Continue traversal...

Final Result:
[3,3,5,5,6,7]

Monotonic Deque Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Each element enters and leaves deque at most once.

Space Complexity: O(k)
Explanation:
Deque stores window indices.

Edge Cases

Window size = 1
Window size = array length
Duplicate values
Negative numbers
Increasing and decreasing arrays

Why This Problem is Important

Sliding Window Maximum helps in understanding:
Monotonic deque
Sliding window optimization
Range maximum queries
Efficient traversal
Queue-based optimization
It is one of the most important deque interview problems.

Real-World Applications

Sliding window concepts are used in:
Stock market analysis
Signal processing
Real-time analytics
Temperature monitoring
Streaming systems

Common Mistakes

Forgetting expired indices
Incorrect deque ordering
Storing values instead of indices
Wrong window formation condition

Interview Tips

Interviewers often expect:
Monotonic deque explanation
O(n) optimization reasoning
Sliding window understanding
Always explain:
why deque remains decreasing
why front stores maximum
how expired indices are removed

Related Questions

First Negative Integer in Window
Shortest Subarray with Sum ≥ K
Constrained Subsequence Sum
Sliding Window Median
Daily Temperatures

Final Takeaway

The Sliding Window Maximum problem is a fundamental monotonic deque problem that teaches efficient range maximum processing and sliding window optimization techniques. Understanding this problem builds a strong foundation for advanced deque and sliding window interview problems.

Sliding Window Maximum

Example 1

Constraints

Hints: