Sliding Window on Arrays in DSA C#

Mental Model

We look at a small part of the array at a time and move this part step by step to cover the whole array.

Analogy: Imagine looking through a small window on a long fence. You see only a few fence boards at once, then slide the window to see the next few boards without moving back.

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

Dry Run Walkthrough

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

Goal: Find the sum of each window of size 3 as it slides from start to end

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

Window covers: [1][3][2][5][7][2]
               ↑  ↑  ↑

Why: We need the initial sum to start sliding

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

Window covers: [1][3][2][5][7][2]
                  ↑  ↑  ↑

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

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

Window covers: [1][3][2][5][7][2]
                     ↑  ↑  ↑

Why: Continue sliding window to cover next part

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

Window covers: [1][3][2][5][7][2]
                        ↑  ↑  ↑

Why: Final window covers last 3 elements

Result:

Sums: 6, 10, 14, 14

Annotated Code

DSA C#

using System;

class SlidingWindow {
    public static void PrintWindowSums(int[] arr, int k) {
        if (arr == null || arr.Length < k || k <= 0) {
            Console.WriteLine("Invalid input");
            return;
        }

        int windowSum = 0;
        // Calculate sum of first window
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        Console.Write(windowSum);

        // Slide the window from start to end
        for (int i = k; i < arr.Length; i++) {
            windowSum += arr[i] - arr[i - k];
            Console.Write(", " + windowSum);
        }
        Console.WriteLine();
    }

    static void Main() {
        int[] arr = {1, 3, 2, 5, 7, 2};
        int k = 3;
        PrintWindowSums(arr, k);
    }
}

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

Calculate initial sum of the first window

for (int i = k; i < arr.Length; i++) { windowSum += arr[i] - arr[i - k];

Slide window by removing left element and adding new right element

Output

6, 10, 14, 14

Complexity Analysis

Time: O(n) because we calculate the sum for the first window 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 sums each window from scratch in O(k) time, leading to O(n*k) total, which is slower than this O(n) sliding window method

Edge Cases

window size larger than array length

Prints 'Invalid input' and stops

DSA C#

if (arr == null || arr.Length < k || k <= 0) { Console.WriteLine("Invalid input"); return; }

window size is zero or negative

Prints 'Invalid input' and stops

DSA C#

if (arr == null || arr.Length < k || k <= 0) { Console.WriteLine("Invalid input"); return; }

array is empty

Prints 'Invalid input' and stops

DSA C#

if (arr == null || arr.Length < k || k <= 0) { Console.WriteLine("Invalid input"); return; }

When to Use This Pattern

When you need to process all subarrays of fixed size efficiently, reach for the sliding window pattern because it avoids repeated work by updating results incrementally.

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 cases where window size is zero or larger than array length
Fix: Add input validation to check window size before processing

Summary

Calculates values over a moving fixed-size part of an array efficiently.

Use when you need to examine all subarrays of a certain size without repeated full calculations.

The key is to update the result by removing the old element and adding the new one as the window slides.

Practice

1. What is the main purpose of the sliding window technique when working with arrays?

easy

A. To efficiently find subarray sums or properties without recalculating everything each time

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 the sliding window concept

   The sliding window technique moves a fixed-size window over the array to calculate values like sums or averages efficiently.

2. Step 2: Identify the purpose

   It avoids recalculating the sum or property for each new window by updating the previous result, making it efficient.

3. Final Answer:

   To efficiently find subarray sums or properties without recalculating everything each time -> Option A

4. Quick Check:

   Sliding window = efficient subarray calculation [OK]

Hint: Think of a moving window updating results fast [OK]

Common Mistakes:

• Confusing sliding window with sorting
• Thinking it reverses arrays
• Assuming it finds max element globally

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

easy

A. for (int i = 1; i <= arr.Length - k; i++)

B. for (int i = 0; i <= arr.Length - k; i++)

C. for (int i = k; i < arr.Length; i++)

D. for (int i = 0; i < arr.Length + k; i++)

Solution

1. Step 1: Determine valid window start indices

   The window of size k can start at index 0 up to index arr.Length - k to avoid overflow.

2. Step 2: Check loop condition

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

3. Final Answer:

   for (int i = 0; i <= arr.Length - k; i++) -> Option B

4. Quick Check:

   Loop runs from 0 to arr.Length - k [OK]

Hint: Window ends at arr.Length - k index [OK]

Common Mistakes:

• Using < instead of <= causing last window skip
• Starting loop at 1 instead of 0
• Looping beyond array length causing errors

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

int[] arr = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int k = 5;
int maxSum = 0;
int windowSum = 0;

for (int i = 0; i < k; i++)
    windowSum += arr[i];
maxSum = windowSum;

for (int i = k; i < arr.Length; i++) {
    windowSum += arr[i] - arr[i - k];
    if (windowSum > maxSum)
        maxSum = windowSum;
}
Console.WriteLine(maxSum);

medium

A. 16

B. 17

C. 18

D. 20

Solution

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

   Sum of arr[0..4] = 1+3+2+6+(-1) = 11

2. Step 2: Slide window and update sums

   Next windows and sums: - i=5: windowSum = 11 + 4 - 1 = 14 (maxSum=14) - i=6: windowSum = 14 + 1 - 3 = 12 (maxSum=14) - i=7: windowSum = 12 + 8 - 2 = 18 (maxSum=18) - i=8: windowSum = 18 + 2 - 6 = 14 (maxSum=18)

3. Final Answer:

   18 -> Option C

4. Quick Check:

   Max sliding window sum = 18 [OK]

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

Common Mistakes:

• Not subtracting the element leaving the window
• Starting loop from wrong index
• Incorrect initial sum calculation

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

int maxSum = 0;
int windowSum = 0;
for (int i = 0; i < arr.Length; i++) {
    windowSum += arr[i];
    if (i >= k) {
        windowSum -= arr[i - k];
        if (windowSum > maxSum)
            maxSum = windowSum;
    }
}
Console.WriteLine(maxSum);

medium

A. maxSum should be initialized to int.MinValue to handle negative sums

B. The if condition should be i > k instead of i >= k

C. The loop should start from i = k instead of 0

D. windowSum should be reset to 0 inside the loop

Solution

1. Step 1: Analyze maxSum initialization

   maxSum is 0 initially, which fails if all sums are negative because maxSum will never update.

2. Step 2: Correct initialization for negative values

   Initialize maxSum to int.MinValue to correctly track maximum sum even if negative.

3. Final Answer:

   maxSum should be initialized to int.MinValue to handle negative sums -> Option A

4. Quick Check:

   maxSum init = int.MinValue for negatives [OK]

Hint: Use int.MinValue for max tracking with negatives [OK]

Common Mistakes:

• Initializing maxSum to 0 causes wrong max for negative arrays
• Changing loop start incorrectly
• Resetting windowSum inside loop breaks sliding window

5. Given an array of integers, write a sliding window approach to find the length of the longest subarray with sum less than or equal to S. Which of the following describes the correct approach?

hard

A. Use a stack to store elements and pop when sum exceeds S

B. Sort the array and use binary search to find subarrays with sum ≤ S

C. Calculate sum of all subarrays and pick the longest with sum ≤ S

D. Use two pointers to expand and shrink the window, updating sum and max length accordingly

Solution

1. Step 1: Use two pointers to represent window boundaries

   Start both pointers at the beginning and expand the right pointer to include elements while sum ≤ S.

2. Step 2: Shrink window from left when sum exceeds S

   If sum > S, move left pointer forward subtracting elements until sum ≤ S again, tracking max length.

3. Final Answer:

   Use two pointers to expand and shrink the window, updating sum and max length accordingly -> Option D

4. Quick Check:

   Two-pointer sliding window for variable length subarray [OK]

Hint: Expand right, shrink left to keep sum ≤ S [OK]

Common Mistakes:

• Sorting array breaks original order needed
• Checking all subarrays is inefficient
• Using stack is not suitable for sum constraints