Sliding Window on Arrays in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the sliding window technique in arrays?

A method to create a 'window' of fixed size that moves over the array to process elements efficiently without reprocessing the entire window each time.

beginner

Why is sliding window more efficient than nested loops for fixed-size subarray problems?

Because it reuses previous computations by adding the new element and removing the old one from the window, avoiding repeated work and reducing time complexity.

intermediate

In a sliding window of size k, how do you update the window when moving from index i to i+1?

Remove the element at index i from the window and add the element at index i+k to the window.

beginner

What is a common use case of sliding window on arrays?

Finding the maximum or minimum sum of any subarray of size k, or checking for a pattern within a fixed-size window.

intermediate

How does sliding window help in problems like 'Longest substring without repeating characters'?

It dynamically adjusts the window size to maintain a valid substring by moving the start and end pointers, efficiently tracking characters without rechecking the entire substring.

What does the sliding window technique primarily help to optimize?

A Memory usage by storing all subarrays

B Time complexity by avoiding repeated calculations

C Sorting the array before processing

D Recursion depth in algorithms

Sliding window reduces time complexity by reusing previous computations instead of recalculating sums or values for each subarray.

In a fixed-size sliding window of size k, how many elements are added and removed when the window moves one step?

A 1 element added and 1 removed

B k elements added and k removed

C No elements added or removed

D k elements added and none removed

When the window moves by one position, one new element enters and one old element leaves the window.

Which problem can be solved using sliding window?

A Find factorial of a number

B Sort an array

C Traverse a binary tree

D Find maximum sum of subarray of size k

Sliding window is ideal for fixed-size subarray problems like finding maximum sum.

What is the initial step in applying sliding window on an array?

A Sort the array

B Find the minimum element

C Calculate the sum of the first window

D Reverse the array

You start by calculating the sum or value of the first window before sliding it.

Sliding window technique is especially useful when the window size is:

A Fixed and known

B Variable and unknown

C Always equal to array length

D Zero

Sliding window works best with a fixed window size to efficiently move and update the window.

Explain how the sliding window technique works on arrays with an example.

Think about how you move a frame over a list and update what’s inside without starting over.

Describe a real-life scenario where sliding window technique can be applied.

Imagine watching a moving window on a conveyor belt or monitoring recent data points.

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