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

Recall & Review

beginner

What is the sliding window technique in arrays?

It is a method to create a 'window' of fixed size that moves over the array to solve problems efficiently by avoiding repeated work.

intermediate

How does the sliding window technique improve performance compared to a naive approach?

It reduces time complexity by reusing previous computations instead of recalculating for every new window, often changing O(n*k) to O(n).

beginner

In a sliding window of size k, how do you update the sum when moving the window by one position?

Subtract the element leaving the window and add the new element entering the window.

intermediate

What kind of problems can be solved using the sliding window technique?

Problems involving subarrays or substrings like maximum sum of k elements, longest substring without repeating characters, or minimum size subarray sum.

advanced

Explain the difference between fixed-size and variable-size sliding windows.

Fixed-size windows have a constant length moving over the array, while variable-size windows can expand or shrink based on conditions to solve more complex problems.

What is the main advantage of using a sliding window over nested loops for subarray problems?

A It uses more memory to store all subarrays

B It always finds the global maximum

C It reduces time complexity by avoiding repeated calculations

D It sorts the array first

Sliding window avoids recalculating sums or values for overlapping parts, reducing time complexity.

In a fixed-size sliding window of size k, how many elements do you add and remove when the window moves one step?

A Add 1 element, remove 1 element

B Add 0 elements, remove 1 element

C Add 1 element, remove 0 elements

D Add k elements, remove k elements

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

Which of these problems is best suited for the sliding window technique?

A Finding the sum of all elements in the array

B Finding the maximum sum of any subarray of size k

C Finding the maximum element in the entire array

D Sorting the array

Sliding window efficiently finds sums or values in subarrays of fixed size.

What does a variable-size sliding window allow you to do that a fixed-size window does not?

A Change the window size dynamically based on conditions

B Move the window backwards

C Sort the window elements

D Skip elements in the array

Variable-size windows expand or shrink to meet problem constraints.

If you want to find the longest substring without repeating characters, which technique is most suitable?

A Binary search

B Fixed-size sliding window

C Sorting

D Sliding window with variable size

Variable-size sliding window adjusts size to avoid repeats.

Describe how the sliding window technique works on arrays and why it is useful.

Think about how you can avoid recalculating sums for every subarray.

Explain the difference between fixed-size and variable-size sliding windows with examples.

Consider problems where window size must adjust to conditions.

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