Sliding Window on Arrays in DSA C

Mental Model

A sliding window moves over the array to look at a small part at a time, updating results without starting over.

Analogy: Imagine looking through a small window on a long fence and sliding it step by step to see different parts without moving back.

Array: [1] [2] [3] [4] [5] [6] [7] [8]
Window size 3:
[1] [2] [3] ↑window
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Dry Run Walkthrough

Input: array: [1, 3, 2, 6, 4, 5], window size: 3

Goal: Find the sum of every window of size 3 in the array

Step 1: Calculate sum of first window [1, 3, 2]

Window: [1] [3] [2] -> sum = 6

Why: We need a starting sum to slide the window forward

Step 2: Slide window right by 1: remove 1, add 6

Window: [3] [2] [6] -> sum = 6 - 1 + 6 = 11

Why: Update sum efficiently without re-adding all elements

Step 3: Slide window right by 1: remove 3, add 4

Window: [2] [6] [4] -> sum = 11 - 3 + 4 = 12

Why: Keep updating sum as window moves

Step 4: Slide window right by 1: remove 2, add 5

Window: [6] [4] [5] -> sum = 12 - 2 + 5 = 15

Why: Final window sum calculated

Result:

Window sums: 6, 11, 12, 15

Annotated Code

DSA C

#include <stdio.h>

void sliding_window_sum(int arr[], int n, int k) {
    if (k <= 0 || k > n) {
        // No valid windows
        return;
    }
    int window_sum = 0;
    // Calculate sum of first window
    for (int i = 0; i < k; i++) {
        window_sum += arr[i];
    }
    printf("%d", window_sum);
    // Slide the window from start to end
    for (int i = k; i < n; i++) {
        window_sum = window_sum - arr[i - k] + arr[i];
        printf(", %d", window_sum);
    }
    printf("\n");
}

int main() {
    int arr[] = {1, 3, 2, 6, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    sliding_window_sum(arr, n, k);
    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 = window_sum - arr[i - k] + arr[i]; }

Slide window by removing left element and adding new right element

Output

6, 11, 12, 15

Complexity Analysis

Time: O(n) because we calculate the first window sum once and then update sums in constant time for each slide

Space: O(1) because we only store the current window sum and no extra arrays

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

Edge Cases

window size k is 0

No windows to sum, function prints nothing or zero sums

DSA C

if (k <= 0 || k > n) { return; }

window size k is greater than array length

No valid windows, function prints nothing

DSA C

if (k <= 0 || k > n) { return; }

array with one element and window size 1

Prints the single element as the only window sum

DSA C

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

When to Use This Pattern

When you need to process all subarrays or parts of fixed size efficiently, use sliding window to avoid repeated work.

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

Summary

Calculates results over fixed-size parts of an array by moving a window step-by-step.

Use when you want to find sums, averages, or other aggregates over all subarrays of a fixed size efficiently.

The key is to update the result by removing the old element and adding the new one instead of recalculating everything.

Practice

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

easy

A. To efficiently process subarrays of fixed size without recomputing 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 the main use

   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 A

4. Quick Check:

   Sliding window = efficient subarray processing [OK]

Hint: Sliding window avoids repeated work on overlapping subarrays [OK]

Common Mistakes:

• Thinking it sorts the array
• Assuming it reverses elements
• Confusing it with finding max of whole array

2. Which of the following is the correct syntax to initialize a sliding window sum for the first k elements in C?

easy

A. int sum = 0; for(int i = 1; i <= k; i++) sum += arr[i];

B. int sum = arr[0] + arr[k];

C. int sum = 0; for(int i = 0; i < k; i++) sum += arr[i];

D. int sum = arr[k]; for(int i = 0; i < k; i++) sum += arr[i];

Solution

1. Step 1: Check loop range for first k elements

   The loop should start at 0 and run while i < k to cover first k elements.

2. Step 2: Verify sum initialization and accumulation

   Sum starts at 0 and adds arr[i] for each i in 0 to k-1.

3. Final Answer:

   int sum = 0; for(int i = 0; i < k; i++) sum += arr[i]; -> Option C

4. Quick Check:

   Loop 0 to k-1 sums first k elements [OK]

Hint: Loop from 0 to k-1 to sum first k elements [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Adding arr[k] which is outside first k elements
• Initializing sum incorrectly

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

int arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int 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 < 9; i++) {
    window_sum += arr[i] - arr[i - k];
    if(window_sum > max_sum) max_sum = window_sum;
}
printf("%d", max_sum);

medium

A. 18

B. 16

C. 17

D. 15

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 = 18

3. Final Answer:

   18 -> Option A

4. Quick Check:

   Max sliding window sum = 18 [OK]

Hint: Update sum by adding new and subtracting old element [OK]

Common Mistakes:

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

4. Identify the error in the following sliding window code snippet and choose the correct fix:

int arr[] = {2, 1, 5, 1, 3, 2};
int k = 3;
int window_sum = 0;
for(int i = 0; i <= k; i++) window_sum += arr[i];
for(int i = k; i < 6; i++) {
    window_sum += arr[i] - arr[i - k];
    printf("%d ", window_sum);
}

medium

A. No error, code is correct

B. Change loop condition to i < k in second for loop

C. Initialize window_sum to arr[0]

D. Change loop condition to i < k in first for loop

Solution

1. Step 1: Check first loop range for initial sum

   Loop runs i = 0 to i = k (inclusive), so 4 elements summed instead of 3.

2. Step 2: Fix loop condition to sum exactly k elements

   Change condition to i < k to sum first 3 elements only.

3. Final Answer:

   Change loop condition to i < k in first for loop -> Option D

4. Quick Check:

   Initial sum must cover exactly k elements [OK]

Hint: Use i < k to sum first k elements, not i <= k [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Changing wrong loop's condition
• Assuming initialization error

5. Given an array of integers and a window size k, how would you find the minimum sum of any contiguous subarray of size k using the sliding window technique?

hard

A. Sort the array and pick first k elements to sum

B. Initialize sum of first k elements, slide window updating sum and track minimum sum found

C. Use nested loops to check all subarrays and find minimum sum

D. Reverse the array and sum last k elements

Solution

1. Step 1: Calculate initial sum of first k elements

   Sum the first k elements to start the sliding window.

2. Step 2: Slide window across array updating sum and track minimum

   For each new element, add it and subtract the element leaving the window, update minimum sum if current sum is smaller.

3. Final Answer:

   Initialize sum of first k elements, slide window updating sum and track minimum sum found -> Option B

4. Quick Check:

   Sliding window tracks sums efficiently to find minimum [OK]

Hint: Track min sum by updating window sum while sliding [OK]

Common Mistakes:

• Sorting array instead of sliding window
• Using nested loops causing inefficiency
• Ignoring elements leaving the window