Sliding Window on Arrays in DSA Java

Mental Model

A sliding window moves over an array to look at a small part at a time, updating as it goes without starting over.

Analogy: Imagine looking through a small window on a long fence, moving it step by step to see different parts without lifting it off.

Array: [1] [2] [3] [4] [5] [6] [7]
Window size 3:
[1] [2] [3] ↑window
[ ] [ ] [ ] [ ] [ ] [ ] [ ]

Dry Run Walkthrough

Input: array: [2, 1, 5, 2, 3, 2], window size: 3

Goal: Find the maximum sum of any 3 consecutive numbers in the array

Step 1: Calculate sum of first window [2,1,5]

Window: [2] [1] [5] -> sum=8

Why: We need a starting sum to compare with next windows

Step 2: Slide window by 1: remove 2, add 2 (next element)

Window: [1] [5] [2] -> sum=8

Why: Update sum efficiently by removing left and adding right element

Step 3: Slide window by 1: remove 1, add 3

Window: [5] [2] [3] -> sum=10

Why: Check if new window sum is larger

Step 4: Slide window by 1: remove 5, add 2

Window: [2] [3] [2] -> sum=7

Why: Continue sliding to check all windows

Result:

Maximum sum window: [5] [2] [3] -> sum=10

Annotated Code

DSA Java

public class SlidingWindow {
    public static int maxSumSubarray(int[] arr, int k) {
        if (arr == null || arr.length < k) return -1;
        int maxSum = 0, windowSum = 0;
        // Calculate sum of first window
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        maxSum = windowSum;
        // Slide the window from start to end
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k];
            if (windowSum > maxSum) {
                maxSum = windowSum;
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 2, 3, 2};
        int k = 3;
        int result = maxSumSubarray(arr, k);
        System.out.println("Maximum sum of " + k + " consecutive elements: " + result);
    }
}

for (int i = 0; i < k; i++) { windowSum += arr[i]; }

Calculate initial sum of the first window

for (int i = k; i < arr.length; i++) { windowSum += arr[i] - arr[i - k];

Slide window by removing left element and adding new right element

if (windowSum > maxSum) { maxSum = windowSum; }

Update max sum if current window sum is larger

Output

Maximum sum of 3 consecutive elements: 10

Complexity Analysis

Time: O(n) because we traverse the array once, updating sums in constant time per step

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Naive approach sums each window from scratch in O(k) time, leading to O(n*k) total, which is slower than sliding window's O(n)

Edge Cases

Array length less than window size

Returns -1 indicating invalid input

DSA Java

if (arr == null || arr.length < k) return -1;

Array with all negative numbers

Still finds the maximum sum window correctly

DSA Java

maxSum initialized after first window sum calculation

Window size equals array length

Returns sum of entire array as only window

DSA Java

for (int i = 0; i < k; i++) { windowSum += arr[i]; }

When to Use This Pattern

When asked to find sums or averages of consecutive elements efficiently, use sliding window to avoid repeated summing.

Common Mistakes

Mistake: Recalculating sum of each window from scratch inside the loop
Fix: Use sliding window update: add new element and subtract old element to update sum in O(1)

Summary

Finds max sum of k consecutive elements by moving a window over the array.

Use when you need to process all subarrays of fixed size efficiently.

Keep track of sum by adding new element and removing old one instead of recomputing.

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