Sliding Window on Arrays in DSA C++

Mental Model

A sliding window moves over the array to consider a subset of elements at a time, updating the result efficiently without redoing work.

Analogy: Imagine looking through a small window on a long fence. You slide the window along the fence to see different parts without moving the whole fence.

Array: [1] [2] [3] [4] [5] [6] [7]
Window:      ↑-----↑
             indexes 1 to 3

Dry Run Walkthrough

Input: array: [2, 1, 5, 2, 3, 2], window size k=3

Goal: Find the maximum sum of any subarray of size 3

Step 1: Calculate sum of first window (indexes 0 to 2)

Window elements: [2, 1, 5], sum = 8

Why: We need a starting sum to compare with next windows

Step 2: Slide window right by 1: remove 2, add 2 (indexes 1 to 3)

Window elements: [1, 5, 2], sum = 8 - 2 + 2 = 8

Why: Update sum efficiently by removing left and adding right element

Step 3: Slide window right by 1: remove 1, add 3 (indexes 2 to 4)

Window elements: [5, 2, 3], sum = 8 - 1 + 3 = 10

Why: Keep updating sum to find max without recalculating entire window

Step 4: Slide window right by 1: remove 5, add 2 (indexes 3 to 5)

Window elements: [2, 3, 2], sum = 10 - 5 + 2 = 7

Why: Final window sum to compare for max

Result:

Maximum sum of any window size 3 is 10

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxSumSlidingWindow(const vector<int>& arr, int k) {
    int n = arr.size();
    if (n < k || k == 0) return 0; // handle edge cases

    int window_sum = 0;
    // Calculate sum of first window
    for (int i = 0; i < k; ++i) {
        window_sum += arr[i];
    }
    int max_sum = window_sum;

    // Slide the window from start to end
    for (int i = k; i < n; ++i) {
        window_sum += arr[i] - arr[i - k]; // update sum by removing left and adding right
        max_sum = max(max_sum, window_sum); // update max if current sum is bigger
    }

    return max_sum;
}

int main() {
    vector<int> arr = {2, 1, 5, 2, 3, 2};
    int k = 3;
    cout << maxSumSlidingWindow(arr, k) << "\n";
    return 0;
}

for (int i = 0; i < k; ++i) { window_sum += arr[i]; }

Calculate initial sum of the first window

for (int i = k; i < n; ++i) { window_sum += arr[i] - arr[i - k]; max_sum = max(max_sum, window_sum); }

Slide window forward by one: remove left element, add right element, update max

Output

10

Complexity Analysis

Time: O(n) because we traverse the array once, updating the window sum in constant time each step

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

vs Alternative: Naive approach recalculates sum for each window in O(k) time, leading to O(n*k) total, which is slower than sliding window's O(n)

Edge Cases

Empty array or window size zero

Returns 0 immediately as no windows can be formed

DSA C++

if (n < k || k == 0) return 0;

Window size larger than array length

Returns 0 because no valid window exists

DSA C++

if (n < k || k == 0) return 0;

All negative numbers

Still returns the maximum sum among windows, which may be negative

DSA C++

max_sum = max(max_sum, window_sum);

When to Use This Pattern

When you need to find something over all subarrays of fixed size efficiently, use sliding window to avoid repeated work and achieve linear time.

Common Mistakes

Mistake: Recalculating the sum of the window from scratch on every slide
Fix: Update the sum by subtracting the element leaving the window and adding the new element entering

Mistake: Not handling edge cases like empty array or window size zero
Fix: Add checks at the start to return 0 or handle invalid inputs

Summary

Finds the maximum sum of any subarray of fixed size by moving a window across the array.

Use when you need to process 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 recalculating.

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