Sliding Window on Arrays in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to slide the window by moving the start index forward.

DSA C++

start = 0;
for (int end = 0; end < n; ++end) {
    if (end - start + 1 > k) {
        start [1];
    }
}

Drag options to blanks, or click blank then click option'

A++start

B--start

Cstart++

Dstart--

Attempts:

3 left

💡 Hint

Common Mistakes

Decreasing start index instead of increasing it.

Using post-increment which works but is less clear here.

To slide the window forward, we increase the start index by one using ++start.

2fill in blank

medium

Complete the code to add the current element to the window sum.

DSA C++

int window_sum = 0;
for (int end = 0; end < n; ++end) {
    window_sum [1] arr[end];
}

Drag options to blanks, or click blank then click option'

A-=

B/=

C*=

D+=

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition.

Using multiplication or division which changes the sum incorrectly.

We add the current element to the window sum using the += operator.

3fill in blank

hard

Fix the error in the condition to check if the window size equals k.

DSA C++

if (end - start [1] k - 1) {
    // process window
}

Drag options to blanks, or click blank then click option'

A<=

B>=

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using > or < instead of == causes wrong window size checks.

Forgetting the -1 adjustment in the condition.

The window size is (end - start + 1). To check if it equals k, use end - start == k - 1.

4fill in blank

hard

Fill both blanks to correctly update the window sum when sliding the window.

DSA C++

window_sum [1] arr[end];
window_sum [2] arr[start];

Drag options to blanks, or click blank then click option'

A+=

B-=

C*=

D/=

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong operators causes incorrect sums.

Forgetting to subtract the old element.

Add the new element with += and subtract the old element with -= to update the sum.

5fill in blank

hard

Fill all three blanks to create a map of word lengths for words longer than 3 characters.

DSA C++

std::map<std::string, int> lengths;
for (const auto& word : words) {
    if (word.size() [1] 3) {
        lengths[[2]] = [3];
    }
}

Drag options to blanks, or click blank then click option'

A>

Bword

Cword.size()

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= instead of > in condition.

Swapping key and value in the map.

Check if word size is greater than 3, then map word to its length.

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