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

Recall & Review

beginner

What is the main idea behind the Sliding Window technique on arrays?

It involves creating a 'window' (a subset of elements) that slides over the array to efficiently solve problems involving contiguous elements without reprocessing the entire window each time.

intermediate

How does the Sliding Window technique improve performance compared to a naive approach?

It reduces repeated work by updating the window incrementally (adding the new element and removing the old one) instead of recalculating from scratch, often changing time complexity from O(n*k) to O(n).

beginner

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

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

beginner

What is a common use case for the Sliding Window technique?

Finding the maximum or minimum sum of any contiguous subarray of size k, or checking for a substring with certain properties in strings.

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, useful for problems like finding the smallest subarray meeting a condition.

What is the time complexity of a sliding window approach for finding the maximum sum of subarrays of size k?

A O(n*k)

B O(n^2)

C O(k)

D O(n)

Sliding window updates the sum by adding one element and removing another, so it processes the array in linear time O(n).

Which of the following is NOT a characteristic of the sliding window technique?

A Processes contiguous elements

B Recalculates the entire window sum every time

C Moves the window one step at a time

D Optimizes repeated calculations

Sliding window avoids recalculating the entire window sum every time by updating incrementally.

In a variable-size sliding window, what determines when to shrink the window?

A When a condition is met or violated

B When the window reaches a fixed length

C After a fixed number of steps

D When the array ends

Variable-size windows adjust size based on conditions, shrinking when the condition is violated or met.

Which problem can be solved efficiently using sliding window?

A Calculating factorial

B Sorting an array

C Finding the longest substring without repeating characters

D Binary search in a sorted array

Sliding window helps find substrings with certain properties, like longest substring without repeats.

What does the 'window' represent in the sliding window technique?

A A subset of contiguous elements

B The entire array

C A fixed pointer in the array

D A random selection of elements

The window is a contiguous subset of elements that moves through the array.

Describe how the sliding window technique works for finding the maximum sum of any subarray of size k.

Think about how to avoid recalculating the sum from scratch each time.

Explain the difference between fixed-size and variable-size sliding windows and give an example problem for each.

Consider how window size changes during the process.

Practice

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

easy

A. To find the maximum element in the entire array

B. To sort the array in ascending order

C. To efficiently process subarrays of fixed size without recomputing everything

D. To reverse the array elements

Solution

1. Step 1: Understand the sliding window concept

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

2. Step 2: Identify the purpose

   It avoids recomputing sums or other values for each subarray by updating results incrementally.

3. Final Answer:

   To efficiently process subarrays of fixed size without recomputing everything -> Option C

4. Quick Check:

   Sliding window = efficient fixed-size subarray processing [OK]

Hint: Think of a moving window that updates results quickly [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to start a sliding window loop of size k over an array arr of length n in C++?

easy

A. for (int i = k; i < n; i++)

B. for (int i = 0; i < n; i += k)

C. for (int i = 0; i < n + k; i++)

D. for (int i = 0; i <= n - k; i++)

Solution

1. Step 1: Determine valid window start indices

   The window of size k can start at indices from 0 up to n-k to fit inside the array.

2. Step 2: Check loop condition

   The loop must run while i <= n-k to include the last valid window.

3. Final Answer:

   for (int i = 0; i <= n - k; i++) -> Option D

4. Quick Check:

   Loop runs from 0 to n-k inclusive [OK]

Hint: Window start max index = n - k [OK]

Common Mistakes:

• Using i < n instead of i <= n-k
• Incrementing i by k skips windows
• Starting loop at k instead of 0

3. What is the output of the following C++ code?

int arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int n = 9, k = 5;
int max_sum = 0, window_sum = 0;
for (int i = 0; i < k; i++) {
    window_sum += arr[i];
}
max_sum = window_sum;
for (int i = k; i < n; i++) {
    window_sum += arr[i] - arr[i - k];
    if (window_sum > max_sum) max_sum = window_sum;
}
std::cout << max_sum << std::endl;

medium

A. 18

B. 17

C. 16

D. 19

Solution

1. Step 1: Calculate initial window sum of first 5 elements

   Sum = 1+3+2+6+(-1) = 11

2. Step 2: Slide window and update sums

   Next windows:
   i=5: sum=11+4-1=14
   i=6: sum=14+1-3=12
   i=7: sum=12+8-2=18
   i=8: sum=18+2-6=14
   Max sum found is 18

3. Final Answer:

   18 -> Option A

4. Quick Check:

   Max sliding window sum = 18 [OK]

Hint: Add new element, subtract old element in window [OK]

Common Mistakes:

• Not subtracting the element leaving the window
• Incorrect initial sum calculation
• Off-by-one errors in loop limits

4. Identify the bug in this sliding window code that finds the minimum sum of subarrays of size k:

int min_sum = INT_MAX, window_sum = 0;
for (int i = 0; i < n; i++) {
    window_sum += arr[i];
    if (i >= k) {
        window_sum -= arr[i - k - 1];
    }
    if (i >= k - 1 && window_sum < min_sum) {
        min_sum = window_sum;
    }
}

medium

A. The subtraction should happen when i >= k, but the subtraction index is off by one

B. The subtraction should happen when i >= k - 1, not i >= k

C. The subtraction should happen when i >= k, but loop should start from i = 1

D. The condition should be i > k instead of i >= k

Solution

1. Step 1: Check subtraction timing

   The condition if (i >= k) for subtraction is correct; it starts after the first full window of size k.

2. Step 2: Identify the index bug

   The code subtracts arr[i - k - 1], but it should be arr[i - k]. This is off-by-one; for i = k, it subtracts arr[-1] instead of arr[0].

3. Final Answer:

   The subtraction should happen when i >= k, but the subtraction index is off by one -> Option A

4. Quick Check:

   Index i - k - 1 causes arr[-1] access [OK]

Hint: Check when subtraction starts and which element is removed [OK]

Common Mistakes:

• Starting subtraction too early or too late
• Using wrong index for subtraction
• Not updating min_sum correctly

5. Given an array arr and an integer k, how would you find the maximum average of any subarray of size k using the sliding window technique?

hard

A. Calculate sum of all subarrays of size k and divide each by k, then find max average

B. Use sliding window to find max sum of subarrays of size k, then divide max sum by k

C. Sort the array and take average of last k elements

D. Use two nested loops to check all subarrays and keep track of max average

Solution

1. Step 1: Use sliding window to find max sum of size k

   Sliding window efficiently finds max sum by adding new element and removing old one.

2. Step 2: Calculate max average from max sum

   Divide the max sum by k to get the maximum average.

3. Final Answer:

   Use sliding window to find max sum of subarrays of size k, then divide max sum by k -> Option B

4. Quick Check:

   Max average = max sum / k using sliding window [OK]

Hint: Find max sum first, then divide by k for average [OK]

Common Mistakes:

• Sorting array instead of using sliding window
• Using nested loops causing inefficiency
• Dividing sums incorrectly