Sliding Window Maximum Using Deque in DSA Go - Execution Trace

Concept Flow - Sliding Window Maximum Using Deque

Start with empty deque

↓

For each element in array

↓

Remove indices from front if out of window

↓

Remove indices from back if current element is greater

↓

Add current index to back

↓

If window is formed, record max from front

↓

Repeat until end of array

We keep indexes of useful elements in a deque. Remove out-of-window and smaller elements to keep max at front.

Execution Sample

DSA Go

nums := []int{1,3,-1,-3,5,3,6,7}
k := 3
// Use deque to find max in each sliding window
for i := 0; i < len(nums); i++ {
  // Remove out-of-window indices
  // Remove smaller elements
  // Add current index
  // Record max if window formed
}

This code finds the maximum in each sliding window of size k using a deque to track indices.

Execution Table

Step	Operation	Deque Indices	Deque Values	Window Max	Visual State
1	Add index 0 (value 1)	[0]	[1]	-	Deque: [1]
2	Add index 1 (value 3), remove 0 (1) since 3>1	[1]	[3]	-	Deque: [3]
3	Add index 2 (value -1)	[1,2]	[3,-1]	3	Window [1,3,-1], Max=3
4	Add index 3 (value -3), remove none	[1,2,3]	[3,-1,-3]	3	Window [3,-1,-3], Max=3
5	Add index 4 (value 5), remove 3(-3), 2(-1), 1(3)	[4]	[5]	5	Window [-1,-3,5], Max=5
6	Add index 5 (value 3)	[4,5]	[5,3]	5	Window [-3,5,3], Max=5
7	Add index 6 (value 6), remove 5(3), 4(5)	[6]	[6]	6	Window [5,3,6], Max=6
8	Add index 7 (value 7), remove 6(6)	[7]	[7]	7	Window [3,6,7], Max=7
9	End of array	[7]	[7]	-	Final max list: [3,3,5,5,6,7]

💡 Reached end of array, all sliding windows processed.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
i	0	1	2	3	4	5	6	7	8	8
Deque Indices	[]	[0]	[1]	[1,2]	[1,2,3]	[4]	[4,5]	[6]	[7]	[7]
Window Max List	[]	[]	[]	[3]	[3,3]	[3,3,5]	[3,3,5,5]	[3,3,5,5,6]	[3,3,5,5,6,7]	[3,3,5,5,6,7]

Key Moments - 3 Insights

Why do we remove indices from the back of the deque when the current element is greater?

Because smaller elements behind the current one cannot be maximum in future windows, removing them keeps deque max at front (see steps 2,5,7,8 in execution_table).

Why do we remove indices from the front of the deque when they are out of the current window?

Because those indices represent elements no longer in the sliding window, so they can't be max (step 5 shows removal of old indices).

Why do we store indices instead of values in the deque?

Indices help track if elements are out of the window range and allow access to their values for comparison (visible in deque indices and values columns).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which indices were removed from the deque before adding index 4?

A [1,2,3]

B [0,1]

C [2,3]

D [3,4]

💡 Hint

Check the 'Operation' and 'Deque Indices' columns at step 5 in execution_table.

At which step does the first window maximum get recorded?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Window Max' column in execution_table to see when the first max appears.

If the window size k was 4 instead of 3, how would the 'Window Max' column change at step 3?

A It would record max at step 3 as now window size is larger

B It would record max earlier at step 2

C It would not record max at step 3 because window not formed yet

D No change, max recorded same steps

💡 Hint

Check when window max is recorded relative to window size in execution_table.

Concept Snapshot

Sliding Window Maximum Using Deque:
- Use deque to store indices of elements
- Remove indices out of window front
- Remove smaller elements from back
- Max is at front of deque
- Slide window and record max each step
- Efficient O(n) solution for max in sliding windows

Full Transcript

This visualization shows how to find the maximum value in each sliding window of size k in an array using a deque. We keep indices of elements in the deque, removing those out of the current window from the front and removing smaller elements from the back to keep the largest at the front. At each step, when the window is fully formed, we record the maximum from the front of the deque. The execution table tracks the deque indices, their values, and the maximum for each window. The variable tracker shows how the index pointer and deque change over time. Key moments clarify why we remove elements from front and back and why indices are stored. The quiz tests understanding of these steps. This method efficiently finds sliding window maximums in linear time.

Practice

1. What is the main purpose of using a deque in the Sliding Window Maximum problem?

easy

A. To keep track of indices of elements in the current window in decreasing order of their values

B. To store all elements of the array for quick access

C. To sort the entire array before processing windows

D. To reverse the array elements for easier processing

Solution

1. Step 1: Understand the role of deque

   The deque stores indices of elements in the current window, maintaining them in decreasing order of their values to quickly find the maximum.

2. Step 2: Why not other options?

   Options B, C, and D do not help in efficiently finding the maximum in each sliding window.

3. Final Answer:

   To keep track of indices of elements in the current window in decreasing order of their values -> Option A

4. Quick Check:

   Deque stores indices in decreasing order for max [OK]

Hint: Deque keeps max candidates in order for O(1) max retrieval [OK]

Common Mistakes:

• Using deque to store values instead of indices
• Sorting the entire array instead of using deque
• Not maintaining decreasing order in deque

2. Which Go code snippet correctly initializes an empty deque using a slice for the Sliding Window Maximum problem?

easy

A. deque := make([]int, 5)

B. deque := nil

C. deque := []int{}

D. deque := new([]int)

Solution

1. Step 1: Check initialization methods

   deque := []int{} creates an empty slice which can be used as a deque.

2. Step 2: Why others are incorrect

   make([]int, 5) creates a slice with length 5 filled with zeros, not empty. nil is not initialized. new([]int) returns pointer to nil slice, not usable directly.

3. Final Answer:

   deque := []int{} -> Option C

4. Quick Check:

   Empty slice initialization = deque := []int{} [OK]

Hint: Use empty slice literal []int{} for empty deque [OK]

Common Mistakes:

• Using make with length > 0 creates non-empty slice
• Using nil slice without initialization
• Using new([]int) returns pointer, not slice

3. What is the output of the sliding window maximum for array [1,3,-1,-3,5,3,6,7] with window size 3?

medium

A. [3, 3, 5, 5, 6, 7]

B. [1, 3, -1, -3, 5, 3]

C. [3, -1, -3, 5, 3, 6]

D. [7, 6, 5, 3, -3, -1]

Solution

1. Step 1: Slide window and find max

   Windows and max values: [1,3,-1] -> 3, [3,-1,-3] -> 3, [-1,-3,5] -> 5, [-3,5,3] -> 5, [5,3,6] -> 6, [3,6,7] -> 7

2. Step 2: Collect max values in order

   The output array is [3, 3, 5, 5, 6, 7].

3. Final Answer:

   [3, 3, 5, 5, 6, 7] -> Option A

4. Quick Check:

   Sliding window max = [3, 3, 5, 5, 6, 7] [OK]

Hint: Check max in each window of size 3 [OK]

Common Mistakes:

• Confusing window size or indices
• Taking min instead of max
• Off-by-one errors in window sliding

4. Identify the bug in this Go code snippet for sliding window maximum using deque:

for i := 0; i < len(nums); i++ {
  if len(deque) > 0 && deque[0] <= i-k {
    deque = deque[1:]
  }
  for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[i] {
    deque = deque[:len(deque)-1]
  }
  deque = append(deque, i)
  if i >= k-1 {
    result = append(result, nums[deque[0]])
  }
}

medium

A. The condition deque[0] <= i-k should be deque[0] < i-k+1

B. Deque is not initialized before the loop

C. The loop should start from i = k-1

D. The append to result should happen before deque update

Solution

1. Step 1: Check deque initialization

   The code uses deque but does not show initialization. Without initializing deque as an empty slice, appending will cause runtime error.

2. Step 2: Other parts are correct

   Conditions and loop indices are standard for sliding window maximum. Append to result after deque update is correct.

3. Final Answer:

   Deque is not initialized before the loop -> Option B

4. Quick Check:

   Deque must be initialized before use [OK]

Hint: Always initialize deque slice before appending [OK]

Common Mistakes:

• Forgetting to initialize deque slice
• Incorrect window boundary condition
• Appending result too early

5. Given an array nums = [4, 2, 12, 3, 8, 7, 9] and window size 4, what is the sliding window maximum output using deque? Also, explain why deque helps achieve O(n) time complexity.

hard

A. [12, 3, 8, 7]

B. [12, 12, 8, 9]

C. [4, 12, 12, 9]

D. [12, 12, 12, 9]

Solution

1. Step 1: Calculate sliding window max values

   Windows and max: [4,2,12,3] -> 12, [2,12,3,8] -> 12, [12,3,8,7] -> 12, [3,8,7,9] -> 9

2. Step 2: Explain deque efficiency

   Deque stores indices of elements in decreasing order. Each element is added and removed at most once, so total operations are O(n), avoiding repeated scanning.

3. Final Answer:

   [12, 12, 12, 9] -> Option D

4. Quick Check:

   Sliding window max = [12, 12, 12, 9], deque gives O(n) [OK]

Hint: Deque keeps max candidates, each element processed once [OK]

Common Mistakes:

• Calculating max incorrectly for windows
• Not understanding deque's O(n) benefit
• Confusing window size or indices