Sliding Window Maximum Using Deque in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

A deque helps keep track of indices of elements in the current window in a way that the front always holds the index of the maximum element. It allows efficient insertion and removal from both ends to maintain the window.

intermediate

How does the deque maintain the order of elements for the Sliding Window Maximum?

The deque stores indices of elements in decreasing order of their values. When a new element comes, smaller elements at the back are removed to keep the deque ordered.

beginner

Why do we remove indices from the front of the deque in the Sliding Window Maximum algorithm?

Indices are removed from the front if they are out of the current window's range, ensuring the deque only contains indices within the current window.

intermediate

What is the time complexity of the Sliding Window Maximum algorithm using a deque and why?

The time complexity is O(n) because each element is added and removed from the deque at most once, making the operations linear in total.

beginner

In the Sliding Window Maximum problem, what does the output represent after processing all windows?

The output is a list of maximum values for each sliding window of size k as it moves from the start to the end of the array.

What data structure is best suited for efficiently solving the Sliding Window Maximum problem?

A Deque

B Stack

C Queue

D Hash Map

A deque allows adding and removing elements from both ends efficiently, which is essential for maintaining the sliding window maximum.

When a new element arrives in the sliding window, what happens to smaller elements at the back of the deque?

A They are removed

B They are moved to the front

C They remain unchanged

D They are doubled

Smaller elements at the back are removed to maintain the decreasing order of values in the deque.

Why do we remove indices from the front of the deque during the sliding window process?

A Because they are the largest elements

B Because they are the smallest elements

C Because they are duplicates

D Because they are out of the current window

Indices that fall outside the current window range are removed from the front to keep the deque relevant to the current window.

What does the front of the deque represent at any point in the Sliding Window Maximum algorithm?

A Index of the minimum element in the current window

B Index of the oldest element in the array

C Index of the maximum element in the current window

D Index of the newest element added

The front of the deque always holds the index of the maximum element in the current sliding window.

What is the overall time complexity of the Sliding Window Maximum algorithm using a deque?

A O(n log n)

B O(n)

C O(n^2)

D O(log n)

Each element is pushed and popped at most once, resulting in a linear time complexity O(n).

Explain how a deque is used to find the maximum in each sliding window of size k.

Think about how the deque keeps track of useful elements for each window.

Describe the steps to update the deque when the sliding window moves by one position.

Focus on how the deque changes as the window slides.

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