Sliding Window Maximum Using Deque in DSA Go

Mental Model

Keep track of the largest values in the current window using a special list that quickly removes smaller values.

Analogy: Imagine a line of people waiting to enter a room, but only the tallest people stay in line because shorter ones behind them can't be the tallest in the room.

Array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size k=4
Deque stores indexes of elements in decreasing order of values
Example:
Deque: [4, 5] -> means values [6, 3]
Window: [3, 4, 6, 3]

Dry Run Walkthrough

Input: array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56], window size k=4

Goal: Find the maximum value in every window of size 4 as it slides from left to right

Step 1: Initialize deque and process first 4 elements to build initial window

Array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Deque indexes: [3] -> values [4]
Window covers indexes 0 to 3

Why: We keep only indexes of elements that could be maximum in the current window, removing smaller ones

Step 2: Slide window by 1: remove indexes out of window and add new element 6 at index 4

Deque indexes: [4] -> values [6]
Window covers indexes 1 to 4

Why: Remove indexes outside the window and remove smaller elements before adding new one to keep max at front

Step 3: Slide window by 1: add element 3 at index 5, keep max at front

Deque indexes: [4, 5] -> values [6, 3]
Window covers indexes 2 to 5

Why: 3 is smaller than 6, so it stays behind 6 in deque

Step 4: Slide window by 1: add element 8 at index 6, remove smaller elements before it

Deque indexes: [6] -> values [8]
Window covers indexes 3 to 6

Why: 8 is bigger than 6 and 3, so remove them to keep only potential max

Step 5: Slide window by 1: add element 9 at index 7, remove smaller elements before it

Deque indexes: [7] -> values [9]
Window covers indexes 4 to 7

Why: 9 is bigger than 8, so remove 8 to keep max at front

Step 6: Slide window by 1: add element 10 at index 8, remove smaller elements before it

Deque indexes: [8] -> values [10]
Window covers indexes 5 to 8

Why: 10 is bigger than 9, so remove 9 to keep max at front

Step 7: Slide window by 1: add element 12 at index 9, remove smaller elements before it

Deque indexes: [9] -> values [12]
Window covers indexes 6 to 9

Why: 12 is bigger than 10, so remove 10 to keep max at front

Step 8: Slide window by 1: add element 56 at index 10, remove smaller elements before it

Deque indexes: [10] -> values [56]
Window covers indexes 7 to 10

Why: 56 is bigger than 12, so remove 12 to keep max at front

Result:

Maximums per window: [4, 6, 6, 8, 9, 10, 12, 56]

Annotated Code

DSA Go

package main

import (
	"container/list"
	"fmt"
)

func maxSlidingWindow(nums []int, k int) []int {
	if len(nums) == 0 || k == 0 {
		return []int{}
	}
	result := []int{}
	deque := list.New() // stores indexes

	for i := 0; i < len(nums); i++ {
		// Remove indexes out of current window
		if deque.Len() > 0 && deque.Front().Value.(int) <= i-k {
			deque.Remove(deque.Front())
		}

		// Remove smaller elements from the back
		for deque.Len() > 0 {
			back := deque.Back()
			if nums[back.Value.(int)] < nums[i] {
				deque.Remove(back)
			} else {
				break
			}
		}

		// Add current index
		deque.PushBack(i)

		// Append max to result when first window is ready
		if i >= k-1 {
			result = append(result, nums[deque.Front().Value.(int)])
		}
	}
	return result
}

func main() {
	nums := []int{2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56}
	k := 4
	maxes := maxSlidingWindow(nums, k)
	for i, val := range maxes {
		fmt.Printf("Window %d max: %d\n", i+1, val)
	}
}

if deque.Len() > 0 && deque.Front().Value.(int) <= i-k { deque.Remove(deque.Front()) }

Remove indexes that are out of the current sliding window

for deque.Len() > 0 { back := deque.Back(); if nums[back.Value.(int)] < nums[i] { deque.Remove(back) } else { break } }

Remove smaller elements from the back to keep deque decreasing

deque.PushBack(i)

Add current index to deque as a candidate for max

if i >= k-1 { result = append(result, nums[deque.Front().Value.(int)]) }

Add the front of deque as max for the current window

Output

Window 1 max: 4

Window 2 max: 6

Window 3 max: 6

Window 4 max: 8

Window 5 max: 9

Window 6 max: 10

Window 7 max: 12

Window 8 max: 56

Complexity Analysis

Time: O(n) because each element is added and removed from the deque at most once

Space: O(k) because the deque stores indexes only for the current window size

vs Alternative: Naive approach is O(n*k) by scanning each window fully; deque method is much faster for large arrays

Edge Cases

Empty array or window size zero

Returns empty result immediately

DSA Go

if len(nums) == 0 || k == 0 { return []int{} }

Window size equals array length

Returns single maximum of entire array

DSA Go

if i >= k-1 { result = append(result, nums[deque.Front().Value.(int)]) }

All elements equal

Deque keeps indexes but max is always the same value

DSA Go

for deque.Len() > 0 { back := deque.Back(); if nums[back.Value.(int)] < nums[i] { deque.Remove(back) } else { break } }

When to Use This Pattern

When asked to find max or min in every sliding window efficiently, use the deque pattern to maintain candidates and achieve O(n) time.

Common Mistakes

Mistake: Not removing indexes that fall out of the current window
Fix: Always check and remove front indexes if they are outside the window before processing new element

Mistake: Not removing smaller elements from the back, causing incorrect max
Fix: Remove all smaller elements from the back before adding new index to keep deque decreasing

Summary

Finds maximum values in every sliding window of size k using a deque to track candidates.

Use when you need efficient max/min queries over sliding windows in arrays.

Keep deque indexes in decreasing order of values and remove outdated or smaller elements.

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