Sliding Window Maximum Using Deque in DSA Go - Build from Scratch

Sliding Window Maximum Using Deque

📖 Scenario: Imagine you are analyzing the temperature readings of a city over several days. You want to find the highest temperature recorded in every 3-day window to understand heat trends.

🎯 Goal: Build a Go program that uses a deque (double-ended queue) to find the maximum temperature in every sliding window of size 3 from a list of daily temperatures.

📋 What You'll Learn

Create a slice called temperatures with the exact values: 2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56

Create an integer variable called windowSize and set it to 3

Implement the sliding window maximum logic using a deque represented by a slice of integers called deque

Print the resulting slice of maximum values for each window

💡 Why This Matters

🌍 Real World

Sliding window maximum is used in real-time data analysis, such as monitoring temperature, stock prices, or network traffic to find peaks within a moving time frame.

💼 Career

Understanding sliding window techniques and deque usage is important for software engineers working on performance-critical applications, streaming data processing, and algorithm optimization.

1

Create the temperature data slice

Create a slice called temperatures with these exact integer values: 2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56

DSA Go

# Create the temperatures slice with the exact values
# Your code here

Hint

Use temperatures := []int{...} to create the slice with the exact numbers.

2

Set the sliding window size

Create an integer variable called windowSize and set it to 3

DSA Go

package main

func main() {
    temperatures := []int{2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56}
    // Set the window size to 3
    // Your code here
}

Hint

Use windowSize := 3 to set the size of the sliding window.

3

Implement sliding window maximum using a deque

Create a slice of integers called deque to store indices. Use a for loop with variable i from 0 to len(temperatures). Inside the loop, remove indices from the back of deque while the current temperature is greater than or equal to the temperature at those indices. Remove indices from the front if they are out of the current window. Append i to deque. After the first windowSize - 1 iterations, append the temperature at the front index of deque to a result slice called maxTemps.

DSA Go

package main

func main() {
    temperatures := []int{2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56}
    windowSize := 3

    // Implement sliding window maximum using deque
    // Your code here
}

Hint

Use a slice deque to store indices. Remove smaller elements from the back. Remove front if out of window. Append max values to maxTemps.

4

Print the maximum temperatures for each window

Use fmt.Println(maxTemps) to print the slice maxTemps containing the maximum temperatures for each sliding window.

DSA Go

package main

import "fmt"

func main() {
    temperatures := []int{2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56}
    windowSize := 3

    deque := []int{}
    maxTemps := []int{}

    for i := 0; i = temp at those indices
        for len(deque) > 0 && temperatures[i] >= temperatures[deque[len(deque)-1]] {
            deque = deque[:len(deque)-1]
        }

        // Append current index
        deque = append(deque, i)

        // Remove front if out of window
        if deque[0] = windowSize-1 {
            maxTemps = append(maxTemps, temperatures[deque[0]])
        }
    }

    // Print the maxTemps slice
    // Your code here
}

Hint

Use fmt.Println(maxTemps) to display the final slice of maximum temperatures.

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