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:

  1. Traverse every window
  2. Find maximum element
    inside current window
  3. Store result

This works but repeated scanning increases complexity.

Steps

  1. Traverse all windows.
  2. Scan current window.
  3. Find maximum value.
  4. Store result.
  5. 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:

  1. Remove smaller elements
    from back
  2. Remove out-of-window indices
    from front
  3. Front always stores maximum

This gives:

  • O(n) solution

Steps

  1. Create deque.
  2. Remove smaller elements.
  3. Remove expired indices.
  4. Insert current index.
  5. 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

  1. Window size = 1
  2. Window size = array length
  3. Duplicate values
  4. Negative numbers
  5. Increasing and decreasing arrays

Why This Problem is Important

Sliding Window Maximum helps in understanding:

  1. Monotonic deque
  2. Sliding window optimization
  3. Range maximum queries
  4. Efficient traversal
  5. Queue-based optimization

It is one of the most important deque interview problems.

Real-World Applications

Sliding window concepts are used in:

  1. Stock market analysis
  2. Signal processing
  3. Real-time analytics
  4. Temperature monitoring
  5. Streaming systems

Common Mistakes

  1. Forgetting expired indices
  2. Incorrect deque ordering
  3. Storing values instead of indices
  4. Wrong window formation condition

Interview Tips

Interviewers often expect:

  1. Monotonic deque explanation
  2. O(n) optimization reasoning
  3. Sliding window understanding

Always explain:

  • why deque remains decreasing
  • why front stores maximum
  • how expired indices are removed

Related Questions

  1. First Negative Integer in Window
  2. Shortest Subarray with Sum ≥ K
  3. Constrained Subsequence Sum
  4. Sliding Window Median
  5. 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.