Sliding Window on Arrays in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Sum Subarray of Size K

What is the output of the following C++ code that finds the maximum sum of any subarray of size 3?

DSA C++

int arr[] = {2, 1, 5, 1, 3, 2};
int k = 3;
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 < 6; i++) {
    window_sum += arr[i] - arr[i - k];
    if (window_sum > max_sum) {
        max_sum = window_sum;
    }
}
std::cout << max_sum << std::endl;

A 8

B 6

C 9

D 7

💡 Hint

Think about the sums of all subarrays of size 3 and pick the largest.

The subarrays of size 3 are [2,1,5] sum=8, [1,5,1] sum=7, [5,1,3] sum=9, [1,3,2] sum=6. The maximum sum is 9.

❓ Predict Output

intermediate

Output of Minimum Size Subarray Sum

What is the output of this C++ code that finds the minimum length of a contiguous subarray with sum at least 7?

DSA C++

int arr[] = {2, 3, 1, 2, 4, 3};
int target = 7;
int min_len = 7, sum = 0, start = 0;
for (int end = 0; end < 6; end++) {
    sum += arr[end];
    while (sum >= target) {
        min_len = std::min(min_len, end - start + 1);
        sum -= arr[start];
        start++;
    }
}
if (min_len == 7) min_len = 0;
std::cout << min_len << std::endl;

A 2

B 3

C 4

D 0

💡 Hint

Try to find the smallest window where the sum is at least 7.

The subarray [4,3] has sum 7 and length 2, which is the smallest possible.

🔧 Debug

advanced

Identify the Bug in Sliding Window Maximum Code

What error will this C++ code produce when trying to find the maximum in each sliding window of size 3?

DSA C++

int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
std::deque<int> dq;
for (int i = 0; i < 8; i++) {
    while (!dq.empty() && arr[dq.back()] < arr[i]) {
        dq.pop_back();
    }
    if (!dq.empty() && dq.front() <= i - k) {
        dq.pop_front();
    }
    dq.push_back(i);
    if (i >= k - 1) {
        std::cout << arr[dq.front()] << " ";
    }
}
std::cout << std::endl;

A Outputs: 3 3 5 5 6 7

B Runtime error due to invalid deque access

C Outputs: 1 3 -1 -3 5 3

D No output, infinite loop

💡 Hint

Check the order of conditions when popping from the front of the deque.

The condition to pop from front should be checked before pushing new elements. Here, it is checked after, causing invalid access when dq.front() is out of window.

🧠 Conceptual

advanced

Sliding Window Technique Explanation

Which of the following best describes the sliding window technique on arrays?

A It uses two pointers to create a window that moves over the array to solve problems involving contiguous elements efficiently.

B It sorts the array first and then uses binary search to find elements in subarrays.

C It uses recursion to divide the array into smaller parts and solve each part independently.

D It creates a hash map of all elements and uses it to find duplicates in the array.

💡 Hint

Think about how a window moves over an array without reprocessing all elements.

Sliding window uses two pointers to maintain a window that slides over the array, allowing efficient calculation of sums, maximums, or other properties of contiguous elements.

🚀 Application

expert

Find Number of Subarrays with Sum Exactly K

Given an integer array and an integer k, which approach correctly counts the number of contiguous subarrays that sum exactly to k using a sliding window or prefix sums?

DSA C++

int countSubarraysWithSumK(const std::vector<int>& nums, int k) {
    int count = 0, sum = 0;
    std::unordered_map<int, int> prefixSumCount;
    prefixSumCount[0] = 1;
    for (int num : nums) {
        sum += num;
        if (prefixSumCount.find(sum - k) != prefixSumCount.end()) {
            count += prefixSumCount[sum - k];
        }
        prefixSumCount[sum]++;
    }
    return count;
}

A This code only works for sorted arrays.

B This code uses a sliding window but fails when array contains negative numbers.

C This code counts subarrays with sum less than k, not exactly k.

D This code correctly counts subarrays with sum k using prefix sums and a hash map.

💡 Hint

Consider how prefix sums and hash maps help count subarrays with exact sums.

The code uses prefix sums and a hash map to count how many previous sums equal current sum minus k, thus counting subarrays summing to k efficiently even with negative numbers.

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