Sliding Window Maximum Using Deque in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sliding Window Maximum for a Simple Array

What is the output of the sliding window maximum for the array [1,3,-1,-3,5,3,6,7] with window size 3?

DSA Go

package main

import (
	"container/list"
	"fmt"
)

func maxSlidingWindow(nums []int, k int) []int {
	if len(nums) == 0 {
		return []int{}
	}
	result := []int{}
	deq := list.New()

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

		// Remove smaller values at the end
		for deq.Len() > 0 && nums[deq.Back().Value.(int)] < nums[i] {
			deq.Remove(deq.Back())
		}

		// Add current index
		deq.PushBack(i)

		// Append max to result
		if i >= k-1 {
			result = append(result, nums[deq.Front().Value.(int)])
		}
	}
	return result
}

func main() {
	arr := []int{1,3,-1,-3,5,3,6,7}
	k := 3
	fmt.Println(maxSlidingWindow(arr, k))
}

A [1, 3, -1, -3, 5, 3]

B [7, 6, 5, 3, -3, -1]

C [3, -1, -3, 5, 3, 6]

D [3, 3, 5, 5, 6, 7]

💡 Hint

Remember the sliding window moves one step at a time and the maximum is the largest number in the current window.

The sliding window maximum for the array with window size 3 is calculated by moving the window from left to right and picking the maximum in each window:

• Window [1,3,-1] max is 3
• Window [3,-1,-3] max is 3
• Window [-1,-3,5] max is 5
• Window [-3,5,3] max is 5
• Window [5,3,6] max is 6
• Window [3,6,7] max is 7

❓ Predict Output

intermediate

Sliding Window Maximum Output for Decreasing Array

What is the output of the sliding window maximum for the array [9,8,7,6,5,4,3,2,1] with window size 4?

DSA Go

package main

import (
	"container/list"
	"fmt"
)

func maxSlidingWindow(nums []int, k int) []int {
	if len(nums) == 0 {
		return []int{}
	}
	result := []int{}
	deq := list.New()

	for i := 0; i < len(nums); i++ {
		if deq.Len() > 0 && deq.Front().Value.(int) <= i-k {
			deq.Remove(deq.Front())
		}

		for deq.Len() > 0 && nums[deq.Back().Value.(int)] < nums[i] {
			deq.Remove(deq.Back())
		}

		deq.PushBack(i)

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

func main() {
	arr := []int{9,8,7,6,5,4,3,2,1}
	k := 4
	fmt.Println(maxSlidingWindow(arr, k))
}

A [9, 8, 7, 6, 5, 4]

B [9, 9, 9, 9, 9, 9]

C [6, 5, 4, 3, 2, 1]

D [9, 8, 7, 6, 5, 4, 3, 2]

💡 Hint

In a strictly decreasing array, the first element in each window is the maximum.

Since the array is strictly decreasing, the maximum in each window of size 4 is the first element of that window:

• [9,8,7,6] max is 9
• [8,7,6,5] max is 8
• [7,6,5,4] max is 7
• [6,5,4,3] max is 6
• [5,4,3,2] max is 5
• [4,3,2,1] max is 4

🔧 Debug

advanced

Identify the Bug in Sliding Window Maximum Implementation

What error will this code produce when run, and why? func maxSlidingWindow(nums []int, k int) []int { result := []int{} deq := list.New() for i := 0; i < len(nums); i++ { if deq.Len() > 0 && deq.Front().Value.(int) < i-k { deq.Remove(deq.Front()) } for deq.Len() > 0 && nums[deq.Back().Value.(int)] <= nums[i] { deq.Remove(deq.Back()) } deq.PushBack(i) if i >= k-1 { result = append(result, nums[deq.Front().Value.(int)]) } } return result }

A Runtime panic: interface conversion: interface {} is nil, not int

B Logical error: window maximum values are incorrect

C No error, code runs correctly

D Runtime panic: index out of range

💡 Hint

Check the condition that removes indexes out of the current window.

The condition deq.Front().Value.(int) < i-k is incorrect because it should be <= i-k to remove indexes that are out of the window. This causes old indexes to remain and incorrect maximum values.

🧠 Conceptual

advanced

Why Use a Deque for Sliding Window Maximum?

Why is a deque (double-ended queue) the best data structure to find the sliding window maximum efficiently?

A Because it can store elements in random order for quick access

B Because it uses less memory than arrays

C Because it allows insertion and deletion from both ends in O(1) time, maintaining candidates for maximum efficiently

D Because it sorts the elements automatically as they are inserted

💡 Hint

Think about how the sliding window moves and how we keep track of maximum candidates.

A deque allows adding and removing elements from both ends in constant time. This helps keep indexes of elements that could be maximum in the current window, removing smaller elements from the back and old elements from the front efficiently.

🚀 Application

expert

Find the Number of Maximum Elements in All Sliding Windows

Given an array and window size k, how many times does the maximum element appear across all sliding windows? For example, for array [2,1,3,4,6,3,8,9,10,12,56] and k=4, what is the count of maximum elements appearing in all windows combined?

DSA Go

package main

import (
	"container/list"
	"fmt"
)

func countMaxElements(nums []int, k int) int {
	if len(nums) == 0 {
		return 0
	}
	count := 0
	deq := list.New()

	for i := 0; i < len(nums); i++ {
		if deq.Len() > 0 && deq.Front().Value.(int) <= i-k {
			deq.Remove(deq.Front())
		}

		for deq.Len() > 0 && nums[deq.Back().Value.(int)] < nums[i] {
			deq.Remove(deq.Back())
		}

		deq.PushBack(i)

		if i >= k-1 {
			count++
		}
	}
	return count
}

func main() {
	arr := []int{2,1,3,4,6,3,8,9,10,12,56}
	k := 4
	fmt.Println(countMaxElements(arr, k))
}

A 8

B 11

C 7

D 4

💡 Hint

Count how many sliding windows there are and how many maximum elements appear (one per window).

Each sliding window has exactly one maximum element. The number of sliding windows is (length of array - k + 1). For the given array of length 11 and k=4, number of windows = 11 - 4 + 1 = 8.

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