Why Sliding Window Maximum Using Deque in DSA Go?

The Big Idea

Discover how to find the highest number in every group without checking each group again and again!

The Scenario

Imagine you have a long list of daily temperatures, and you want to find the highest temperature for every 3-day period. Doing this by checking each 3-day group one by one feels like repeating the same work over and over.

The Problem

Manually checking each group means looking at many numbers again and again. This takes a lot of time and can easily cause mistakes, especially if the list is very long.

The Solution

Using a sliding window with a deque helps keep track of the highest numbers smartly. It moves through the list just once, remembering only the important numbers, so it finds the maximum quickly without repeating work.

Before vs After

✗ Before

for i := 0; i <= len(nums)-k; i++ {
    maxVal := nums[i]
    for j := i+1; j < i+k; j++ {
        if nums[j] > maxVal {
            maxVal = nums[j]
        }
    }
    fmt.Println(maxVal)
}

✓ After

deque := []int{}
for i := 0; i < len(nums); i++ {
    // Remove smaller elements from the back
    // Add current element index to the back
    // Remove elements out of window from the front
    // Print front of deque as current max
}

What It Enables

This method lets you find maximum values in moving windows fast and efficiently, even for huge lists.

Real Life Example

Weather apps use this to quickly show the highest temperature in the last few days without slowing down as data grows.

Key Takeaways

Manual checking repeats work and is slow.

Deque keeps track of important values only.

Sliding window maximum finds results fast in one pass.

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