Sliding Window on Arrays in DSA C# - Execution Trace

Concept Flow - Sliding Window on Arrays

Initialize window start and end pointers

↓

Expand window by moving end pointer

↓

Check window size or condition

↓

Process window

↓

Slide window by moving start pointer

↓

Repeat until end reaches array end

The sliding window moves over the array by expanding the end pointer and sliding the start pointer to maintain a fixed window size or condition.

Execution Sample

DSA C#

int[] arr = {1, 3, 2, 5, 8, 2, 6};
int windowSize = 3;
for (int start = 0; start <= arr.Length - windowSize; start++) {
    int sum = 0;
    for (int end = start; end < start + windowSize; end++) {
        sum += arr[end];
    }
    Console.WriteLine(sum);
}

Calculates and prints the sum of every subarray of size 3 using a sliding window.

Execution Table

Step	Operation	Window Start	Window End	Window Elements	Sum	Visual State
1	Initialize window	0	2	[1, 3, 2]	6	1 -> 3 -> 2 -> null
2	Slide window forward	1	3	[3, 2, 5]	10	3 -> 2 -> 5 -> null
3	Slide window forward	2	4	[2, 5, 8]	15	2 -> 5 -> 8 -> null
4	Slide window forward	3	5	[5, 8, 2]	15	5 -> 8 -> 2 -> null
5	Slide window forward	4	6	[8, 2, 6]	16	8 -> 2 -> 6 -> null
6	End reached	-	-	-	-	Window end reached array end, stop

💡 Window end pointer reached the last element of the array, stopping the sliding window.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
start	0	0	1	2	3	4	4
end	2	2	3	4	5	6	6
sum	0	6	10	15	15	16	16
windowElements	[]	[1,3,2]	[3,2,5]	[2,5,8]	[5,8,2]	[8,2,6]	[8,2,6]

Key Moments - 3 Insights

Why does the window end pointer start at index 2 when the window size is 3?

Because the window covers 3 elements starting from index 0, so the end pointer is at start + windowSize - 1, which is 0 + 3 - 1 = 2, as shown in step 1 of the execution_table.

Why do we stop sliding the window when the start pointer reaches index 4?

Because the window size is 3, and the array length is 7, the last valid start index is 7 - 3 = 4. Beyond this, the window would go out of array bounds, as shown in step 6 exit_note.

How is the sum updated when the window slides forward?

In this example, the sum is recalculated fully for each window, but in optimized sliding window, we subtract the element leaving the window and add the new element entering. Here, each sum is shown in the sum column in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the sum of the window elements at step 3?

A 10

B 6

C 15

D 16

💡 Hint

Check the 'Sum' column in row with Step 3 in execution_table.

At which step does the window first include the element '5'?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Window Elements' column in execution_table to find when '5' appears first.

If the window size was 2 instead of 3, how would the 'Window End' pointer change at step 1?

A It would be 1

B It would be 2

C It would be 0

D It would be 3

💡 Hint

Window End = start + windowSize - 1; check variable_tracker for start and windowSize.

Concept Snapshot

Sliding Window on Arrays:
- Use two pointers: start and end
- Window size = fixed length or condition
- Move end pointer to expand window
- Move start pointer to slide window
- Process elements inside window each step
- Efficient for subarray problems like sums, max, min

Full Transcript

Sliding window on arrays uses two pointers to create a moving window over the array elements. The window covers a fixed number of elements or satisfies a condition. We start with the window covering the first elements, then slide it forward by moving the start and end pointers. At each step, we process the elements inside the window, such as calculating their sum. This method avoids repeated work by reusing previous computations. The example code sums every subarray of size 3. The execution table shows how the window moves from start index 0 to 4, with sums calculated at each step. Key points include how the window end pointer is calculated and when the sliding stops. This technique is useful for many array problems requiring continuous subarray processing.

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