Sliding Window Maximum Solution (Leetcode 239)

Pattern Recognition — Sliding Window Maximum (LC239)

1. Identifying the Monotonic Deque Pattern

This pattern applies when:

• Dealing with a fixed-size sliding window over an array or string.
• Need to compute the maximum or minimum (or next greater/smaller) in each window efficiently.
• Constraints demand O(n) time, ruling out naive per-window scans or even heaps.
• The problem involves "streaming" or "real-time" updates as window slides.

Key insight: Maintain a deque of indices where values are in monotonic order (decreasing for max, increasing for min). This allows O(1) access to the extremum while efficiently discarding irrelevant elements.

2. ASCII Flow Example

Let's visualize the deque for nums = [1,3,-1,-3,5], k=3 step-by-step:

nums indices: 0:1, 1:3, 2:-1, 3:-3, 4:5

Start: deque = []

i=0:
- Add 0
Deque: front |0| back  (value 1)

i=1:
- 3 > nums[0]=1 → pop back 0
- Add 1
Deque: |1| (3)

i=2:
- -1 < nums[1]=3 → no pop
- Add 2
Deque: |1|2| (3 > -1)
- i>=2, max = nums[1]=3 for window 0-2

i=3:
- Front 1 >= 3-3+1=1? Yes, keep.
- -3 < nums[2]=-1 → no pop
- Add 3
Deque: |1|2|3| (3 > -1 > -3)
- max = nums[1]=3 for window 1-3

i=4:
- Front 1 < 4-3+1=2? Pop 1
Deque: |2|3|
- 5 > nums[3]=-3 → pop 3
- 5 > nums[2]=-1 → pop 2
- Add 4
Deque: |4| (5)
- max = nums[4]=5 for window 2-4
  

Notice how the deque "cleans" itself: out-of-window from front, useless smaller from back. Front always points to the current max index.

3. Step-by-Step Recognition Checklist

• Is there a fixed window size k sliding over the array? ✅
• Do we need the max/min in each window? ✅
• Are constraints large (n=1e5), needing better than O(nk) or O(n log k)? ✅
• Does the problem allow negatives or duplicates, ruling out simple pointers? ✅
• If yes to all, this is a monotonic deque problem.

4. Comparison with Other Patterns

Problem	Pattern Type	Technique	Window Size	Time Complexity
Two Sum (LC1)	Hash Map Complement	Single pass check	No window	O(n)
Minimum Window Substring (LC76)	Variable-Size Sliding Window	Two pointers, frequency map, expand/shrink dynamically	Variable	O(n)
Subarray Sum Equals K (LC560)	Prefix Sum + Hash Map	Cumulative sum difference	Variable (subarrays)	O(n)
Sliding Window Maximum (LC239)	Monotonic Deque	Decreasing deque of indices, clean front/back	Fixed k	O(n)

Note: Fixed window with max uses deque; variable with conditions uses pointers/map. Deque is "monotonic" like stack in next greater, but for windows.

5. Beginner-Friendly Tips

• Always store indices in deque, not values, to validate window bounds (i - k + 1 <= index <= i).
• Pop back while new element is greater or equal (for max) to handle duplicates — keeps the leftmost index.
• Think: "The deque holds potential future maxes; if a bigger comes, smaller ones are obsolete."
• Practice variations: for min, use increasing deque (pop if new <= back).
• FAANG tip: Interviewers may ask "Why not multiset?" (O(n log k)) or "Adapt for k varying?"
• Use ASCII to track: Label "front (max)" and "back (smallest candidate)".

6. Key Keywords That Hint Monotonic Deque

In problem statements or interviews, look for:

• "sliding window maximum/minimum"
• "fixed-size k window"
• "efficient O(n) max query per slide"
• "monotonic queue/deque"
• "remove useless elements"
• Follow-ups like "next greater in window"

If "variable window", think pointers/map instead.

Interview-Focused — Short Answer to Deliver (Sliding Window Maximum)

"The brute-force way is to scan each of the n-k+1 windows for the max, taking O(nk) time, which is too slow for n=10^5. Instead, use a monotonic deque to maintain indices in decreasing order of values. For each new element, remove out-of-window from front and smaller elements from back, then add the new index. The front is always the max. This is O(n) time since each element is added/removed at most once. Space is O(k)."

One-Minute Checklist to Say

• Explain brute-force O(nk) and why it fails large inputs.
• Describe monotonic deque: decreasing order, store indices, clean front for window, back for larger new elements.
• State complexity: O(n) time, O(k) space.
• Do a short dry-run on [1,3,-1], k=3 showing deque changes.
• Mention edge cases like k=1 (return nums), decreasing sequence (deque size k), duplicates (pop >=).
• FAANG tip: Compare to max-heap (O(n log k)) and why deque better.

Interview Script & What to Say (Sliding Window Maximum)

Step-by-Step Script (Word-for-Word Suggestions)

1. "Let me confirm the problem: Given nums of size n and k, return array of maxes for each sliding window of size k. Output size n-k+1. Constraints: n up to 1e5, k up to n, negatives allowed. Assume one pass?"
2. "A brute-force approach: For i from 0 to n-k, find max in nums[i..i+k-1] using a loop, O(k) per window, total O(nk). Correct but times out for large n,k."
3. "To optimize, use a monotonic deque storing indices in decreasing value order. For each i: 1) If front index out of window (i-k), pop front. 2) While back value < nums[i], pop back (smaller can't be max anymore). 3) Add i to back. 4) If i >= k-1, add nums[front] to result. This is O(n) time, each index in/out once."
4. "Let's dry-run on nums=[1,3,-1,-3,5,3,6,7], k=3: Show step-by-step deque changes (use ASCII if board), explain why pops happen, get [3,3,5,5,6,7]."
5. "Edge cases: k=1 → return nums; k=n → single max; all decreasing → deque accumulates up to k; all increasing → deque often size 1; duplicates → pop if >= to keep leftmost; empty nums → empty result."
6. "Follow-ups: For min, use increasing deque. Why not heap? O(n log k) slower. Space O(k)."

What the Interviewer Hears

• You understand constraints and scale (O(n) need).
• You start with baseline, optimize logically with deque rationale.
• Detailed dry-run shows mastery; edges show thoroughness.
• Ready for FAANG variants like "adapt for streaming" or "next greater in window".

Solution Approach — Sliding Window Maximum (LC239)

1. Problem Restatement

Compute the maximum in each fixed-size k sliding window over nums. Output array of these maxes. Example: [1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]. Must be efficient for n=1e5.

2. Core Idea

• Use a monotonic decreasing deque to store indices of potential max candidates in the current window.
• As we iterate i from 0 to n-1:
• Clean front: If deque.front == i - k, pop front (out of window).
• Clean back: While deque not empty and nums[deque.back] < nums[i], pop back (smaller useless now).
• Add i to back.
• If i >= k-1, append nums[deque.front] to result (current max).
• This keeps deque with valid, decreasing candidates; front always max.

3. ASCII Deque Flow (Full Example)

nums = [1, 3, -1, -3, 5, 3, 6, 7]
indices= 0  1   2    3  4 5 6 7
k=3, result = []

i=0: deque=[]
  - Add 0
  Deque: |0| (1)

i=1:
  - nums[1]=3 > nums[0]=1 → pop 0
  - Add 1
  Deque: |1| (3)

i=2:
  - nums[2]=-1 < 3 → add 2
  Deque: |1 2| (3 > -1)
  - i=2 >=2, result += nums[1]=3 → [3]

i=3:
  - Front 1 >=3-3+1=1 OK
  - nums[3]=-3 < nums[2]=-1 → add 3
  Deque: |1 2 3| (3 > -1 > -3)
  - result += 3 → [3,3]

i=4:
  - Front 1 <4-3+1=2? Pop 1
  Deque: |2 3|
  - nums[4]=5 > -3 → pop 3
  - 5 > -1 → pop 2
  - Add 4
  Deque: |4| (5)
  - result +=5 → [3,3,5]

i=5:
  - Front 4 >=5-3+1=3 OK
  - nums[5]=3 <5 → add 5
  Deque: |4 5| (5 >3)
  - result +=5 → [3,3,5,5]

i=6:
  - Front 4 >=6-3+1=4 OK
  - nums[6]=6 >3 → pop 5
  - 6 >5 → pop 4
  - Add 6
  Deque: |6| (6)
  - result +=6 → [3,3,5,5,6]

i=7:
  - Front 6 >=7-3+1=5 OK
  - nums[7]=7 >6 → pop 6
  - Add 7
  Deque: |7| (7)
  - result +=7 → [3,3,5,5,6,7]
  

This full ASCII trace shows every step: cleaning, popping, adding, and when to record max. Notice how pops ensure only relevant candidates remain.

4. JavaScript Step-by-Step Dry Run

// Function: slidingWindowMaximum
function maxSlidingWindow(nums, k) {
  if (nums.length === 0 || k === 0) return [];
  const deque = []; // Array as deque: shift() front, pop()/push() back
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // Step 1: Remove out-of-window from front
    if (deque.length > 0 && deque[0] === i - k) {
      deque.shift(); // O(1) amortized if using proper deque, but in JS array shift is O(n) worst, but for interviews OK or use linked list
    }

    // Step 2: Remove smaller from back (maintain decreasing)
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop(); // Remove useless smaller candidates
    }

    // Step 3: Add current index to back
    deque.push(i);

    // Step 4: If window formed (i >= k-1), add current max (front) to result
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

// Dry Run Call: maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3) → [3,3,5,5,6,7]
  

In JS, array as deque: push/pop back O(1), shift front O(n) worst, but since total shifts = n, overall O(n). For strict O(1), use custom deque.

5. Step-by-Step Explanation

1. Initialize: Deque empty, result empty.
2. For each i:
1. Clean front: If front index <= i - k, it's left the window — pop to keep only current window indices.
2. Clean back: While new nums[i] >= nums[back], pop back. Why? Smaller elements can't be max while this larger one is in window later.
3. Add i: Always add current index to back, as it could be max for future windows.
4. Record max: Once full window (i >= k-1), front is guaranteed max — add nums[front] to result.
3. Return result: Array of maxes.

FAANG note: Explain why >= for pop: To handle duplicates, keep the leftmost (earliest) index for correct window max.

6. Key Beginner Takeaways

• Deque ensures front = max, back = smallest candidate.
• Visualize with ASCII for each i: window bounds, deque state, pops/adds reason.
• Amortized analysis: Total pops/pushes = O(n), as each index once in/out.
• Compare to other: Unlike prefix sum (sums), this for extremes in windows.
• Practice: Implement for min (change < to > in pop condition).

Deep Dive — Sliding Window Maximum (LC239)

1. Correctness Invariant

At the end of processing each i, the deque contains indices from the current window [i-k+1, i] in decreasing order of nums values. The front is always the index of the maximum in that window, and all elements are valid (no out-of-window).

Why holds: Window check removes old, back clean removes smaller (preserving order), add keeps it monotonic.

2. Why Monotonic Deque Works (In-Depth)

• Monotonic Property: Deque values nums[deque[j]] > nums[deque[j+1]] for all j, so front max.
• Window Maintenance: Pop front if deque[0] < i - k + 1, ensuring within bounds.
• Optimality: Pop back smaller because if a larger element is added, the smaller one can't be max in any future window containing the larger (since larger dominates).
• Amortized Time: Each index added once, removed once (either out-window or smaller) — total O(n).
• Visual Explanation with ASCII for Why Pop Smaller:

Suppose window [1, -1], add 5:
Deque before add: |0|1| (1 > -1)
5 > -1 → pop 1
5 > 1 → pop 0
Add index of 5
Why? If kept -1 or 1, but 5 is larger and will stay longer, so they never max while 5 in window.
    

3. Variants & Trade-Offs

• Minimum in Window: Change pop condition to nums[i] <= nums[back] (increasing deque), front is min.
• Variable Window: Not directly, but combine with pointers for "max in variable range".
• Streaming Data: Maintain deque as data arrives, output max on query.
• 2D or Multi-Dim: Extend to matrix max in submatrices (harder, use 2D deque).
• Trade-Offs: Deque O(n) time/O(k) space vs Heap O(n log k) time/O(k) space — deque faster constant. For very large k, deque worse space if full.
• FAANG Variants: "Find first greater in window" or "kth largest in window" (use min-heap of size k).

4. Micro-Optimizations

• Use array/deque structure with O(1) front/back ops (in JS, array OK; in C++, std::deque).
• Only start recording result after i >= k-1.
• Avoid unnecessary checks: if deque empty, no pop.
• For duplicates, pop >= to prefer left index (correct for multiple same max).
• In languages with overflow, use long for sums if variant, but here not needed.
• Pre-allocate result array size n-k+1.

5. Proof Sketch

Induction: Assume after i-1, deque correct for window [i-1-k+1, i-1]. For i: - Add i: Remove smaller back — maintains decreasing, as new is compared to back. - Remove old front if needed — maintains window. - Front max: Any larger would have popped smaller earlier; no larger missed as all in deque or popped if smaller. Total time: Each index pushed/popped O(1) times.

6. Beginner Takeaways

• Invariant is key: Deque decreasing, in-window → front max.
• Always simulate full example with ASCII to internalize pops/adds.
• FAANG prep: Explain proof, why O(n), variants like min or next greater.
• Compare: For sums, use prefix; for counts, map; for max, deque.
• Practice coding: Implement, test edges, time it on large n.

Common Pitfalls — Sliding Window Maximum

1. Storing Values Instead of Indices

Can't check out-of-window without indices; duplicates hard to handle.

Bad: deque = [3, -1] — how know if 3 still in window?
Good: deque = [1,2] — check if 1 >= i-k+1.
  

2. Incorrect Pop Back Condition

Use nums[i] >= nums[back] for max (handle equals); < for strict may keep unnecessary duplicates.

nums=[3,3], k=2
If > only, deque=[0,1] (3=3 no pop), front 0 correct.
But if later larger, need to keep leftmost.
Actually >= to pop equals if want, but for max OK either, but standard >= to clean.
  

3. Adding to Result Before Full Window

If add when i < k-1, partial window max wrong.

4. Off-by-One in Window Check

deque[0] == i - k (not i - k + 1 sometimes); i starts 0.

i=2, k=3, window 0-2, pop if <0 (none).
i=3, pop if ==0 (if front=0).
Formula: if deque[0] <= i - k → pop.
  

5. Not Handling Duplicates Properly

If not pop equals, multiple same max, but front may be old.

6. Empty Deque Checks

Always check length before access front/back.

7. FAANG Common: Forgetting Amortized Analysis

Explain why O(n): "Each index en/dequeued once."

Beginner Tips

• Dry-run on paper with indices/values.
• Test: decreasing (deque full), increasing (pops all), duplicates.
• Debug: Print deque after each i.
• Avoid: Using stack (no front pop easy).

Edge Cases — Sliding Window Maximum

1. Minimal Input (k=1)

Windows are single elements.

nums = [1,-1,0], k=1 → [1,-1,0]
Deque: Always single index per i, since pop smaller not trigger for single.
  

2. Full Array Window (k=n)

One window, overall max.

nums = [1,3,-1], k=3 → [3]
Deque builds to [1] (3 as max).
  

3. Decreasing Sequence

Deque accumulates all, front always left max.

nums = [5,4,3,2,1], k=3
Deque at i=2: [0,1,2] (5>4>3), max=5
i=3: pop if 0==3-3=0? Pop 0, [1,2,3] (4>3>2), max=4
Etc. Output [5,4,3]
  

4. Increasing Sequence

Deque often size 1, constant pops.

nums = [1,2,3,4,5], k=3
i=2: deque=[2] (3 popped 2,1)
max=3
i=3: pop none, 4>3 pop 2, add 3, deque=[3]
max=4
  

5. Duplicates in Sequence

Pop equals to keep leftmost.

nums = [1,3,3,-1], k=3
i=0: [0]
i=1: 3>1 pop, [1]
i=2: 3==nums[1]=3, pop if >=, pop 1, add 2 [2]
i=3: -1<3 add [2,3], max=3
  

6. All Equal Elements

Deque keeps leftmost, pops as window slides.

nums = [2,2,2,2], k=2 → [2,2,2]
With >= pop, deque size 1 always.
  

7. Empty or Invalid

nums=[], k=1 → [] k > n → invalid, but constraints prevent.

8. Negative and Zero Mix

nums=[-7,-8,0,-1], k=2 → [ -7,0,0 ] Max can be negative or zero.

Interview Demonstration Tips

• Use ASCII board for deque flow on all edges.
• Explain why each pop: "Out of window" or "Smaller, useless".
• Show O(n) by counting total operations.
• FAANG: Discuss if k very large, deque vs other DS.

Time & Space Complexity — Sliding Window Maximum

For FAANG, always explain with big-O and constants; why optimal.

1. Brute-Force Approach

Loop n-k+1 times, each find max in k elements.

for (int i = 0; i <= n - k; i++) {
  int max = Integer.MIN_VALUE;
  for (int j = i; j < i + k; j++) max = Math.max(max, nums[j]);
  result.add(max);
}
  

• Time: O(n * k) — For n=1e5, k=1e5, 1e10 ops, timeout.
• Space: O(1) + output O(n-k+1).
• When mention: Baseline correctness, but inefficient.

2. Priority Queue (Max-Heap)

Maintain heap of k elements, but to remove old, need lazy delete or tree map.

Use PriorityQueue (max-heap) with pairs (value, index).
Add new, remove if front not max or out.
But standard Java PQ remove O(n), so O(n^2) worst.
Better: TreeMap or double PQ with lazy delete.
  

• Time: O(n log k) with proper impl.
• Space: O(k)
• When mention: If deque not recalled, but deque better O(n).

3. Monotonic Deque (Optimal)

Single pass, maintain deque.

See solution-approach code.
  

• Time: O(n) — Each element pushed/popped exactly once.
• Space: O(k) worst (decreasing seq), O(1) avg.
• FAANG note: Amortized O(1) per i, total O(n).

Memory Usage Example

For decreasing nums=[5,4,3,2,1], k=3:

Deque grows to size 3: [0,1,2] (5>4>3), then slides by popping front.
Max space O(k).
  

Summary Table

Approach	Time	Space	Notes
Brute-Force	O(n k)	O(1)	Simple but timeouts on large inputs; good for explaining correctness.
Max-Heap (Priority Queue)	O(n log k)	O(k)	Works but slower than deque; use if deque forgotten.
Monotonic Deque	O(n)	O(k)	Optimal; each element processed constant times.

Interview Tips

• Always start with brute, explain why slow (calculate ops for constraints).
• Show deque dry-run with ASCII to demonstrate O(n).
• If asked worst space, say O(k) for decreasing, but average O(1).
• FAANG: "Can we do better than O(n)? No, must read all."

Related Problems & Progression — Sliding Window Maximum

Master LC239, then build to variants for pattern recognition in FAANG.

1. Longest Substring Without Repeating Characters (LC3)

• Key Difference: Variable window, no fixed k.
• Optimal Approach: Sliding window with set/map for chars.
• Time: O(n), Space: O(1) charset.
• Interview Tip: Basic window; contrast fixed vs variable.

2. Minimum Window Substring (LC76)

• Extension: Variable window for min substring with all chars.
• Pattern: Two pointers, frequency map.
• Time: O(n), Space: O(1).
• Interview Tip: If LC239 fixed max, LC76 variable contain.

3. Next Greater Element I (LC496)

• Monotonic Stack Variant: Find next greater for elements.
• Approach: Stack decreasing, pop for greater.
• Time: O(n), Space: O(n).
• Tip: Deque like stack but for "window" of all right.

4. Daily Temperatures (LC739)

• Monotonic Stack: Days to warmer temp.
• Time: O(n).
• Tip: Similar pop when warmer (greater).

5. Largest Rectangle in Histogram (LC84)

• Advanced Stack: Monotonic increasing for areas.
• Time: O(n).

Suggested Study Path & Interview Progression

1. Basic sliding window: LC3 (variable no repeat).
2. Variable with conditions: LC76 (min contain).
3. Fixed with max: LC239 (monotonic deque).
4. Monotonic stack: LC496 (next greater), LC739 (temperatures).
5. Advanced: LC84 (histogram), LC901 (stock spanner).
6. Verbalize: "Fixed window max → deque; next greater → stack."

Variant Comparison Table

Interview Tips

• Clarify: Fixed k? Max or min? Streaming?
• Trade-offs: Deque vs heap for time/space.
• Duplicates/negatives in questions.
• Dry-runs for each variant.

FAQs — Sliding Window Maximum (LC239)

From candidate perspective: Answers as if explaining in interview.

1. What is a monotonic deque and how does it work here?

As candidate: "A monotonic deque keeps elements in sorted order, here decreasing for max. It stores indices; front is max index. When adding new, pop smaller back as they won't be max anymore. Pop front if out window. Ensures O(1) max."

2. Why use deque over max-heap?

"Heap O(n log k), deque O(n) since each elem in/out once. Deque also easy remove old via index check."

3. How handle duplicates?

"Pop back if nums[i] >= nums[back], removes equals too, keeps leftmost for correct window max."

4. What if k=1 or k=n?

"k=1: Deque always single, result=nums. k=n: Builds deque for whole, result single max."

5. Why store indices not values?

"To check window: if deque[0] < i-k+1, pop. Values alone can't tell position."

6. Time complexity proof?

"Each i pushed once, popped at most once (out-window or smaller), total O(n) operations."

7. Adapt for minimum?

"Change to increasing: pop if nums[i] <= nums[back], front min."

8. What if array has negatives/zeros?

"Handled naturally, as comparisons work with <0."

9. Common bugs?

"Off-by-one in i-k; not popping >= for duplicates; adding result early."

10. Related to monotonic stack?

"Yes, stack for 'next greater' like LC739; deque adds window slide via front pop."

11. Space worst case?

"O(k), when decreasing sequence, deque holds k indices."

12. Streaming variant?

"Maintain deque as data comes, output max on each add after initial k."