Sliding Window on Arrays in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sliding Window Maximum

What is the output of the following Java code that finds the maximum in each sliding window of size 3?

DSA Java

import java.util.*;
public class Main {
  public static void main(String[] args) {
    int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    List<Integer> result = new ArrayList<>();
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < nums.length; i++) {
      while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
        deque.pollFirst();
      }
      while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
        deque.pollLast();
      }
      deque.offerLast(i);
      if (i >= k - 1) {
        result.add(nums[deque.peekFirst()]);
      }
    }
    System.out.println(result);
  }
}

A [3, 3, 5, 5, 6, 7]

B [1, 3, -1, -3, 5, 3, 6, 7]

C [7, 6, 5, 3, -3, -1]

D [3, -1, -3, 5, 3, 6]

💡 Hint

Think about how the deque stores indices of elements and how it removes smaller elements.

The code uses a deque to keep track of indices of elements in the current window. It removes indices that are out of the window and those whose values are smaller than the current element. The maximum for each window is at the front of the deque.

🧠 Conceptual

intermediate

Sliding Window Sum Calculation

Given an array and a window size k, which formula correctly calculates the sum of the next window using the previous window's sum?

A next_sum = previous_sum + arr[i + k] + arr[i]

B next_sum = previous_sum + arr[i] - arr[i + k]

C next_sum = previous_sum - arr[i + k] + arr[i]

D next_sum = previous_sum - arr[i] + arr[i + k]

💡 Hint

Think about removing the element that slides out and adding the new element that slides in.

To move the window forward by one, subtract the element leaving the window (arr[i]) and add the new element entering the window (arr[i + k]).

🔧 Debug

advanced

Identify the Bug in Sliding Window Minimum Code

What error will the following Java code produce when finding the minimum in each sliding window of size 2?

DSA Java

import java.util.*;
public class Main {
  public static void main(String[] args) {
    int[] nums = {4, 2, 12, 3, 5};
    int k = 2;
    List<Integer> result = new ArrayList<>();
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < nums.length; i++) {
      while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
        deque.pollFirst();
      }
      while (!deque.isEmpty() && nums[deque.peekLast()] > nums[i]) {
        deque.pollLast();
      }
      deque.offerLast(i);
      if (i >= k - 1) {
        result.add(nums[deque.peekFirst()]);
      }
    }
    System.out.println(result);
  }
}

A Logical error: outputs incorrect minimum values

B No error, outputs [2, 2, 3, 3]

C Infinite loop

D IndexOutOfBoundsException

💡 Hint

Check the condition that removes indices out of the current window.

The condition `deque.peekFirst() < i - k` should be `deque.peekFirst() <= i - k` to correctly remove indices outside the window. The current condition fails to remove the index exactly equal to `i - k`, causing the deque to retain outdated indices and produce incorrect minimum values.

🚀 Application

advanced

Find Maximum Average Subarray

Which code snippet correctly finds the maximum average of any subarray of size k in an integer array?

A Use nested loops to calculate average of all subarrays and pick the max.

B Sort the array and pick the largest k elements to calculate average.

C Use a sliding window to sum k elements, update max average by dividing sum by k each step.

D Use a stack to track maximum elements and calculate average.

💡 Hint

Sliding window helps calculate sums efficiently without repeated summation.

Sliding window sums the first k elements, then slides forward by subtracting the element leaving and adding the new element. The max average is updated each time.

❓ Predict Output

expert

Output of Variable Size Sliding Window Code

What is the output of this Java code that finds the length of the longest substring with at most 2 distinct characters?

DSA Java

import java.util.*;
public class Main {
  public static void main(String[] args) {
    String s = "eceba";
    int k = 2;
    Map<Character, Integer> map = new HashMap<>();
    int left = 0, right = 0, maxLen = 0;
    while (right < s.length()) {
      char c = s.charAt(right);
      map.put(c, map.getOrDefault(c, 0) + 1);
      while (map.size() > k) {
        char leftChar = s.charAt(left);
        map.put(leftChar, map.get(leftChar) - 1);
        if (map.get(leftChar) == 0) {
          map.remove(leftChar);
        }
        left++;
      }
      maxLen = Math.max(maxLen, right - left + 1);
      right++;
    }
    System.out.println(maxLen);
  }
}

A 2

B 3

C 4

D 5

💡 Hint

Track the window size while keeping at most 2 distinct characters.

The longest substring with at most 2 distinct characters is "ece" with length 3.

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