Sliding Window on Arrays in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sliding Window Sum Calculation

What is the output of the following Go code that calculates the sum of every sliding window of size 3 in the array?

DSA Go

package main
import "fmt"
func main() {
  arr := []int{1, 3, 2, 6, -1, 4, 1, 8, 2}
  k := 3
  var result []int
  windowSum := 0
  for i := 0; i < len(arr); i++ {
    windowSum += arr[i]
    if i >= k-1 {
      result = append(result, windowSum)
      windowSum -= arr[i-k+1]
    }
  }
  fmt.Println(result)
}

A [6 11 7 9 4 13 11]

B [6 11 7 9 4 13]

C [6 11 7 9 4 13 11 10]

D [6 11 7 9 4 13 12]

💡 Hint

Think about how the window sum moves by adding the new element and removing the oldest element in the window.

The code sums every group of 3 consecutive elements. The sums are: (1+3+2)=6, (3+2+6)=11, (2+6+-1)=7, (6+-1+4)=9, (-1+4+1)=4, (4+1+8)=13, (1+8+2)=11.

🧠 Conceptual

intermediate

Sliding Window Maximum Explanation

Which statement correctly describes the sliding window maximum algorithm for an array?

A It sorts each window to find the maximum, resulting in O(n*k*log k) time complexity.

B It uses a stack to store all elements and pops the smallest to find the maximum.

C It uses a queue to keep track of indices of elements in decreasing order to find the maximum in O(n) time.

D It calculates the maximum by comparing all elements in the window every time, resulting in O(n*k) time.

💡 Hint

Think about how to avoid re-checking all elements in each window.

The sliding window maximum algorithm uses a double-ended queue (deque) to store indices of elements in decreasing order. This allows finding the maximum in O(1) time per window, leading to O(n) overall.

🔧 Debug

advanced

Identify the Bug in Sliding Window Average Code

What error will the following Go code produce when calculating the average of every sliding window of size 4?

DSA Go

package main
import "fmt"
func main() {
  arr := []int{2, 5, 1, 8, 2, 9, 1}
  k := 4
  var result []float64
  windowSum := 0
  for i := 0; i < len(arr); i++ {
    windowSum += arr[i]
    if i >= k {
      windowSum -= arr[i-k]
      avg := float64(windowSum) / float64(k)
      result = append(result, avg)
    }
  }
  fmt.Println(result)
}

A The code produces incorrect averages because of integer division.

B The code prints averages but misses the first window's average.

C The code prints an empty slice because the condition never becomes true.

D The code causes a runtime panic due to index out of range.

💡 Hint

Check the condition that triggers the average calculation and when the first average is appended.

The condition 'if i >= k' delays the first average calculation until after the first window is passed, so the first window's average is never added. The code does not panic and uses float64 for division.

❓ Predict Output

advanced

Output of Sliding Window Minimum Using Deque

What is the output of this Go code that finds the minimum in every sliding window of size 3?

DSA Go

package main
import "fmt"
func main() {
  arr := []int{4, 2, 12, 3, 5, 1, 7}
  k := 3
  var result []int
  var deque []int
  for i := 0; i < len(arr); i++ {
    for len(deque) > 0 && arr[deque[len(deque)-1]] >= arr[i] {
      deque = deque[:len(deque)-1]
    }
    deque = append(deque, i)
    if deque[0] <= i-k {
      deque = deque[1:]
    }
    if i >= k-1 {
      result = append(result, arr[deque[0]])
    }
  }
  fmt.Println(result)
}

A [2 3 3 1 1]

B [2 2 3 5 1]

C [4 2 3 1 1]

D [2 2 3 1 1]

💡 Hint

The deque stores indices of elements in increasing order to track minimums.

The minimums for windows are: (4,2,12)=2, (2,12,3)=2, (12,3,5)=3, (3,5,1)=1, (5,1,7)=1.

🧠 Conceptual

expert

Time Complexity of Sliding Window Algorithms

What is the time complexity of the sliding window maximum algorithm using a deque for an array of length n and window size k?

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

B O(n*k) because each window requires scanning k elements to find the maximum.

C O(n log k) because the deque operations require logarithmic time.

D O(k) because the algorithm only processes the first window.

💡 Hint

Consider how many times each element enters and leaves the deque.

Each element is pushed and popped from the deque at most once, so the total operations are proportional to n, making the time complexity O(n).

Practice

1. What is the main purpose of the sliding window technique on arrays?

easy

A. To efficiently process subarrays of fixed size without re-computing everything

B. To sort the array in ascending order

C. To reverse the array elements

D. To find the maximum element in the entire array

Solution

1. Step 1: Understand sliding window concept

   The sliding window technique moves a fixed-size window over the array to process subarrays efficiently.

2. Step 2: Identify purpose

   It avoids recalculating values for overlapping parts of subarrays, improving performance.

3. Final Answer:

   To efficiently process subarrays of fixed size without re-computing everything -> Option A

4. Quick Check:

   Sliding window = efficient subarray processing [OK]

Hint: Sliding window avoids repeated work on overlapping parts [OK]

Common Mistakes:

• Confusing sliding window with sorting
• Thinking it reverses arrays
• Assuming it finds max of whole array

2. Which of the following Go code snippets correctly initializes a sliding window sum for the first 3 elements of an integer array arr?

easy

A. sum := 0
for i := 0; i < 3; i++ {
sum += arr[i]
}

B. sum := 0
for i := 1; i <= 3; i++ {
sum += arr[i]
}

C. sum := 0
for i := 0; i <= 3; i++ {
sum += arr[i]
}

D. sum := 0
for i := 1; i < 3; i++ {
sum += arr[i]
}

Solution

1. Step 1: Check loop bounds for first 3 elements

   Array indices start at 0, so first 3 elements are at indices 0,1,2. Loop must run i from 0 to less than 3.

2. Step 2: Verify each option

   sum := 0 for i := 0; i < 3; i++ { sum += arr[i] } loops i=0 to 2 correctly. Others either start at 1 or go out of bounds.

3. Final Answer:

   sum := 0 for i := 0; i < 3; i++ { sum += arr[i] } -> Option A

4. Quick Check:

   Loop i=0 to 2 sums first 3 elements [OK]

Hint: Array indices start at 0; loop to i < window size [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= instead of < causing out of bounds
• Incorrect loop end index

3. What is the output of the following Go code?

arr := []int{2, 1, 5, 1, 3, 2}
windowSize := 3
sum := 0
for i := 0; i < windowSize; i++ {
    sum += arr[i]
}
result := []int{sum}
for i := windowSize; i < len(arr); i++ {
    sum += arr[i] - arr[i-windowSize]
    result = append(result, sum)
}
fmt.Println(result)

medium

A. [8 6 9 7]

B. [8 7 9 6 5]

C. [8 7 9 6]

D. [2 1 5 1 3 2]

Solution

1. Step 1: Calculate initial window sum

   First 3 elements: 2+1+5=8. result = [8]

2. Step 2: Slide window and update sums

   i=3: sum=8 + arr[3](1) - arr[0](2) = 8+1-2=7; result=[8,7] i=4: sum=7 + arr[4](3) - arr[1](1) = 7+3-1=9; result=[8,7,9] i=5: sum=9 + arr[5](2) - arr[2](5) = 9+2-5=6; result=[8,7,9,6]

3. Final Answer:

   [8 7 9 6] -> Option C

4. Quick Check:

   Sliding sums = [8 7 9 6] [OK]

Hint: Add new element, subtract old element to update sum [OK]

Common Mistakes:

• Not subtracting the element leaving the window
• Appending sum before updating
• Incorrect initial sum calculation

4. Identify the bug in this Go code that tries to find the maximum sum of any subarray of size 2:

arr := []int{1, 3, 2, 5, 1}
windowSize := 2
maxSum := 0
sum := 0
for i := 0; i < windowSize; i++ {
    sum += arr[i]
}
for i := windowSize; i < len(arr); i++ {
    sum += arr[i] - arr[i-windowSize]
    if sum > maxSum {
        maxSum = sum
    }
}
fmt.Println(maxSum)

medium

A. maxSum should be initialized to a very small number, not 0

B. The first window sum is not compared to maxSum

C. The loop should start from i = 0 in the second loop

D. The subtraction in sum update is incorrect

Solution

1. Step 1: Check initial maxSum and first window sum

   maxSum is 0, sum is sum of first 2 elements (1+3=4). But maxSum is not updated with this initial sum.

2. Step 2: Identify missing comparison

   The first window sum should be compared to maxSum before sliding the window, else maxSum remains 0 if all sums are less.

3. Final Answer:

   The first window sum is not compared to maxSum -> Option B

4. Quick Check:

   Compare initial sum to maxSum before loop [OK]

Hint: Always compare initial window sum to max before sliding [OK]

Common Mistakes:

• Not updating maxSum with initial sum
• Wrong loop start index
• Incorrect sum update formula

5. Given an array of integers, write a Go function using sliding window to find the length of the longest subarray with sum less than or equal to a target value k. Which approach correctly solves this problem?

hard

A. Sort the array and use binary search to find subarrays with sum ≤ k

B. Use a stack to store sums and pop when sum exceeds k

C. Calculate sum of all subarrays and pick the longest with sum ≤ k

D. Use two pointers to expand and shrink the window, updating sum and max length accordingly

Solution

1. Step 1: Understand problem constraints

   We want the longest subarray with sum ≤ k, which requires dynamic window size adjustment.

2. Step 2: Choose sliding window with two pointers

   Expand right pointer adding elements to sum; if sum > k, move left pointer to shrink window until sum ≤ k; track max length.

3. Final Answer:

   Use two pointers to expand and shrink the window, updating sum and max length accordingly -> Option D

4. Quick Check:

   Two-pointer sliding window adjusts size for sum ≤ k [OK]

Hint: Expand right, shrink left when sum exceeds target [OK]

Common Mistakes:

• Sorting array breaks subarray order
• Checking all subarrays is inefficient
• Using stack is not suitable here