Sliding Window on Arrays in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the sliding window technique in arrays?

A method to efficiently process a subset (window) of elements in an array by moving the window step-by-step, avoiding repeated work.

intermediate

How does the sliding window improve performance compared to a nested loop?

It reduces time complexity by updating the window incrementally instead of recalculating the entire window each time, often from O(n*k) to O(n).

beginner

In a fixed-size sliding window, what happens when the window moves forward?

The element leaving the window is removed from calculations, and the new element entering the window is added, updating the result efficiently.

beginner

What is a common use case for a sliding window on arrays?

Finding the maximum or minimum sum of any subarray of size k, or checking for patterns within a continuous subset of elements.

intermediate

Explain the difference between fixed-size and variable-size sliding windows.

Fixed-size windows have a constant length as they slide, while variable-size windows can grow or shrink based on conditions like sum or unique elements.

What does the sliding window technique help to avoid when processing arrays?

A Sorting the array multiple times

B Recalculating the entire window for each step

C Using extra memory for each element

D Ignoring elements outside the window

Sliding window updates the window incrementally, avoiding full recalculation each time.

Which problem is best solved using a sliding window?

A Finding the maximum sum of subarrays of size k

B Sorting an array

C Finding the median of the entire array

D Reversing an array

Sliding window efficiently finds sums or other metrics in continuous subarrays of fixed size.

In a fixed-size sliding window of size 3, how many elements change when the window moves one step forward?

A 2 elements leave and 2 enter

B All 3 elements change

C No elements change

D 1 element leaves and 1 element enters

Only the oldest element leaves and a new element enters the window.

What is the typical time complexity of a sliding window algorithm on an array of length n?

A O(n^2)

B O(log n)

C O(n)

D O(1)

Sliding window algorithms usually run in linear time by processing each element once.

Which of these is NOT a characteristic of a variable-size sliding window?

A Window size is fixed and constant

B Used to find subarrays with certain properties

C Window size changes based on conditions

D Can expand or shrink dynamically

Variable-size windows do not have a fixed size; fixed-size windows do.

Describe how the sliding window technique works on arrays and why it is efficient.

Think about how you slide a small frame over a long row of pictures.

Explain the difference between fixed-size and variable-size sliding windows with examples.

Consider a window that always shows 3 items vs one that grows or shrinks.

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