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

Recall & Review

beginner

What is the sliding window technique in arrays?

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

beginner

How does the sliding window technique improve performance compared to a nested loop?

It reduces time complexity by updating the window incrementally instead of recalculating sums or values from scratch for each position.

beginner

In a fixed-size sliding window, how do you move the window forward?

Remove the element going out of the window from the left and add the new element coming into the window from the right.

intermediate

What is a variable-size sliding window?

A window whose size can grow or shrink based on conditions, often used to find subarrays meeting certain criteria.

beginner

Give an example problem where sliding window is useful.

Finding the maximum sum of any subarray of size k in an array.

What does the sliding window technique help avoid?

A Recursion in array processing

B Recalculating values for overlapping parts of the array

C Using extra memory for a new array

D Sorting the array multiple times

Sliding window updates the window incrementally, avoiding repeated calculations for overlapping elements.

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

A k elements added and k removed

B No elements added or removed

C 1 element added and 1 removed

D k-1 elements added and removed

Only one element leaves the window and one new element enters when sliding by one position.

Which problem is best solved using a variable-size sliding window?

A Find longest substring with at most k distinct characters

B Find max sum of fixed size subarray

C Sort an array

D Find minimum element in array

Variable-size windows adjust size to meet conditions like distinct character count.

What is the time complexity of sliding window technique for an array of size n?

A O(log n)

B O(n log n)

C O(n^2)

D O(n)

Sliding window processes each element at most twice, resulting in linear time.

Which of these is NOT a typical use of sliding window?

A Binary searching in sorted array

B Finding longest substring with constraints

C Finding max/min sum subarray of fixed size

D Counting occurrences in a moving window

Binary search is unrelated to sliding window technique.

Explain how the sliding window technique works for finding the maximum sum of subarrays of size k.

Think about how to avoid recalculating the sum from scratch each time.

Describe the difference between fixed-size and variable-size sliding windows and give an example use case for each.

Consider problems like max sum subarray vs longest substring with constraints.

Practice

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

easy

A. To efficiently find subarray sums or properties without recomputing everything

B. To sort the array elements 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 avoid repeated calculations.

2. Step 2: Identify the main use case

   It helps find sums or other properties of subarrays efficiently by updating the window incrementally.

3. Final Answer:

   To efficiently find subarray sums or properties without recomputing everything -> Option A

4. Quick Check:

   Sliding window = efficient subarray calculation [OK]

Hint: Think of a moving window to avoid repeated work [OK]

Common Mistakes:

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

2. Which of the following Java code snippets correctly initializes a sliding window sum for the first k elements of an array arr?

easy

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

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

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

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

Solution

1. Step 1: Check loop boundaries for summing first k elements

   The loop should run from 0 to k-1 to include exactly k elements.

2. Step 2: Verify each option's loop range

   int sum = 0; for(int i = 0; i < k; i++) sum += arr[i]; loops i from 0 to less than k, summing arr[0] to arr[k-1], which is correct.

3. Final Answer:

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

4. Quick Check:

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

Hint: Loop from 0 to less than k to sum k elements [OK]

Common Mistakes:

• Using <= k causes out-of-bound errors
• Starting loop from 1 misses first element
• Initializing sum with arr[0] and looping incorrectly

3. What will be the output of the following Java code?

int[] arr = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int k = 5;
int maxSum = 0, 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;
    }
}
System.out.println(maxSum);

medium

A. 16

B. 17

C. 18

D. 19

Solution

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

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

2. Step 2: Slide window and update maxSum

   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
• Incorrect initial sum calculation
• Updating maxSum incorrectly

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

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;
    }
}
System.out.println(maxSum);

medium

A. The first loop should run from i = 0 to i < k, not i <= k

B. maxSum should be initialized to Integer.MIN_VALUE

C. The second loop should start from i = k + 1

D. windowSum should be reset to 0 before the second loop

Solution

1. Step 1: Check the first loop boundary

   The first loop runs i from 0 to k inclusive, which sums k+1 elements causing out-of-bounds error.

2. Step 2: Correct loop boundary

   The loop should run from 0 to less than k to sum exactly k elements.

3. Final Answer:

   The first loop should run from i = 0 to i < k, not i <= k -> Option A

4. Quick Check:

   Loop boundary off by one causes error [OK]

Hint: Use < k, not <= k, for k elements [OK]

Common Mistakes:

• Using <= k causes array index out of bounds
• Incorrect initialization of maxSum
• Wrong start index in second loop

5. Given an array of integers, write a Java method using the sliding window technique to find the length of the longest subarray with sum less than or equal to a given value target. Which approach correctly solves this problem?

hard

A. Sort the array and use binary search to find subarrays with sum ≤ target

B. Use two pointers to expand and shrink the window, updating max length when sum ≤ target

C. Use nested loops to check all subarrays and track the longest valid one

D. Use a stack to store sums and pop when sum exceeds target

Solution

1. Step 1: Understand the problem constraints

   We want the longest subarray with sum ≤ target, which requires dynamic window size.

2. Step 2: Apply sliding window with two pointers

   Use two pointers to expand the window adding elements, shrink from left when sum > target, track max length.

3. Final Answer:

   Use two pointers to expand and shrink the window, updating max length when sum ≤ target -> Option B

4. Quick Check:

   Two-pointer sliding window finds longest valid subarray [OK]

Hint: Expand window, shrink when sum too big, track max length [OK]

Common Mistakes:

• Sorting breaks original order, invalid for subarrays
• Nested loops are inefficient for large arrays
• Stack is not suitable for sum-based sliding window