Sliding Window Maximum Using Deque in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the deque for sliding window maximum.

DSA Go

var dq [1]

Drag options to blanks, or click blank then click option'

A[]int

Bint

Cmap[int]int

Dstring

Attempts:

3 left

💡 Hint

Common Mistakes

Using int instead of a slice

Using map instead of slice

The deque is represented as a slice of integers to store indices.

2fill in blank

medium

Complete the code to remove indices from the back of the deque while current element is greater.

DSA Go

for len(dq) > 0 && nums[i] [1] nums[dq[len(dq)-1]] {
    dq = dq[:len(dq)-1]
}

Drag options to blanks, or click blank then click option'

A<

B==

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using < instead of >

Using == which does not remove smaller elements

We remove from the back while current element is greater than elements at those indices.

3fill in blank

hard

Fix the error in removing indices out of the current window from the front of the deque.

DSA Go

if len(dq) > 0 && dq[0] [1]= i - k + 1 {
    dq = dq[1:]
}

Drag options to blanks, or click blank then click option'

A>=

B<

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using < which misses removing equal index

Using > or >= which is incorrect

We remove indices from front if they are out of the window (less than or equal to i-k).

4fill in blank

hard

Fill both blanks to append the current index and record the maximum for the window.

DSA Go

dq = append(dq, [1])
if i >= k-1 {
    result = append(result, nums[dq[[2]]])
}

Drag options to blanks, or click blank then click option'

Ai

B0

Clen(dq)-1

Dk-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(dq)-1 for max index which is wrong

Using k-1 as index

Append current index i; maximum is at front dq[0].

5fill in blank

hard

Fill all three blanks to complete the sliding window maximum function using deque.

DSA Go

func maxSlidingWindow(nums []int, k int) []int {
    var dq [1]
    var result []int
    for i := 0; i < len(nums); i++ {
        for len(dq) > 0 && nums[i] [2] nums[dq[len(dq)-1]] {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)
        if dq[0] [3]= i - k + 1 {
            dq = dq[1:]
        }
        if i >= k-1 {
            result = append(result, nums[dq[0]])
        }
    }
    return result
}

Drag options to blanks, or click blank then click option'

A[]int

B>

C<=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Wrong deque type

Wrong comparison operators causing logic errors

Deque is []int; remove smaller elements with >; remove out-of-window indices with <=.

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