Sliding Window on Arrays in DSA Go

Mental Model

A sliding window moves over the array to look at a small part at a time, updating as it goes.

Analogy: Imagine looking through a small window on a long fence, moving it step by step to see different parts without stepping back.

Array: [1] -> [3] -> [5] -> [2] -> [8] -> [6] -> null
Window size = 3
Window covers: [1] -> [3] -> [5] ↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 2, 8, 6], window size: 3

Goal: Find the maximum sum of any 3 consecutive elements

Step 1: Calculate sum of first window elements (1 + 3 + 5)

[1] -> [3] -> [5] ↑ -> [2] -> [8] -> [6] -> null

Why: We need a starting sum to compare with others

Step 2: Slide window right by one: subtract 1, add 2; new sum = 3 + 5 + 2 = 10

[1] -> [3] -> [5] -> [2] ↑ -> [8] -> [6] -> null

Why: Update sum efficiently without re-adding all elements

Step 3: Slide window right by one: subtract 3, add 8; new sum = 5 + 2 + 8 = 15

[1] -> [3] -> [5] -> [2] -> [8] ↑ -> [6] -> null

Why: Keep moving window to check all groups

Step 4: Slide window right by one: subtract 5, add 6; new sum = 2 + 8 + 6 = 16

[1] -> [3] -> [5] -> [2] -> [8] -> [6] ↑ -> null

Why: Check last possible window

Result:

Final max sum window: [2] -> [8] -> [6] -> null with sum 16

Annotated Code

DSA Go

package main

import "fmt"

func maxSumSlidingWindow(arr []int, k int) int {
    if len(arr) < k || k == 0 {
        return 0
    }

    windowSum := 0
    maxSum := 0

    // Calculate sum of first window
    for i := 0; i < k; i++ {
        windowSum += arr[i]
    }
    maxSum = windowSum

    // Slide the window from start to end
    for i := k; i < len(arr); i++ {
        windowSum += arr[i] - arr[i-k] // update sum by removing left and adding right
        if windowSum > maxSum {
            maxSum = windowSum
        }
    }

    return maxSum
}

func main() {
    arr := []int{1, 3, 5, 2, 8, 6}
    k := 3
    result := maxSumSlidingWindow(arr, k)
    fmt.Printf("Max sum of %d consecutive elements: %d\n", k, result)
}

for i := 0; i < k; i++ { windowSum += arr[i] }

Calculate initial sum of the first window

for i := k; i < len(arr); i++ { windowSum += arr[i] - arr[i-k]

Slide window by removing left element and adding new right element

if windowSum > maxSum { maxSum = windowSum }

Update max sum if current window sum is greater

Output

Max sum of 3 consecutive elements: 16

Complexity Analysis

Time: O(n) because we traverse the array once, updating sums in constant time per step

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Naive approach sums each window from scratch in O(k) per window, leading to O(n*k) time, which is slower

Edge Cases

Empty array or window size zero

Returns 0 immediately as no windows can be formed

DSA Go

if len(arr) < k || k == 0 {
        return 0
    }

Window size larger than array length

Returns 0 because no valid window exists

DSA Go

if len(arr) < k || k == 0 {
        return 0
    }

All negative numbers

Still finds the maximum sum window correctly

DSA Go

if windowSum > maxSum {
            maxSum = windowSum
        }

When to Use This Pattern

When you need to find something over all subarrays of fixed size efficiently, use sliding window to avoid repeated summing.

Common Mistakes

Mistake: Recomputing the sum of each window from scratch inside the loop
Fix: Update the sum by subtracting the element leaving the window and adding the new element entering

Summary

Finds max sum of fixed-size consecutive elements by moving a window over the array.

Use when you want to analyze all subarrays of a fixed length efficiently.

The key is updating the window sum by removing the left element and adding the right element instead of recomputing.

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