Sliding Window on Arrays in DSA Java - Execution Trace

Concept Flow - Sliding Window on Arrays

Initialize window start and end pointers

↓

Expand window by moving end pointer

↓

Check if window size reached desired size

↓

Keep expanding

↓

Slide window by moving start pointer

↓

Repeat until end reaches array end

The sliding window moves over the array by expanding the end pointer until the window size is reached, then processes the window and slides forward by moving the start pointer.

Execution Sample

DSA Java

import java.util.Arrays;

int[] arr = {1, 3, 2, 5, 8, 7};
int k = 3;
for (int end = 0, start = 0; end < arr.length; end++) {
  if (end - start + 1 == k) {
    System.out.println(Arrays.toString(Arrays.copyOfRange(arr, start, end + 1)));
    start++;
  }
}

Prints all subarrays of size k=3 using a sliding window over the array.

Execution Table

Step	Operation	start	end	Window Size	Window Elements	Action
1	Initialize start=0, end=0	0	0	1	[1]	Expand window
2	Move end to 1	0	1	2	[1, 3]	Expand window
3	Move end to 2	0	2	3	[1, 3, 2]	Window size reached k=3, print and slide start
4	Slide start to 1	1	2	2	[3, 2]	Shrink window
5	Move end to 3	1	3	3	[3, 2, 5]	Window size reached k=3, print and slide start
6	Slide start to 2	2	3	2	[2, 5]	Shrink window
7	Move end to 4	2	4	3	[2, 5, 8]	Window size reached k=3, print and slide start
8	Slide start to 3	3	4	2	[5, 8]	Shrink window
9	Move end to 5	3	5	3	[5, 8, 7]	Window size reached k=3, print and slide start
10	Slide start to 4	4	5	2	[8, 7]	Shrink window
11	end=5 reached array end	4	5	2	[8, 7]	Stop

💡 End pointer reached the last element of the array, sliding window complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
start	0	0	0	0	1	1	2	2	3	3	4	4
end	0	0	1	2	2	3	3	4	4	5	5	5
window size	1	1	2	3	2	3	2	3	2	3	2	2
window elements	[1]	[1]	[1,3]	[1,3,2]	[3,2]	[3,2,5]	[2,5]	[2,5,8]	[5,8]	[5,8,7]	[8,7]	[8,7]

Key Moments - 3 Insights

Why do we check if window size equals k before processing?

Because only when the window size reaches k do we have a complete subarray to process, as shown in execution_table rows 3, 5, 7, 9.

Why do we slide the start pointer after processing the window?

Sliding the start pointer shrinks the window from the left to allow the window to move forward, enabling new subarrays, as seen in execution_table rows 4, 6, 8, 10.

What happens if we don't slide the start pointer?

The window size would grow beyond k and not represent the fixed size subarray we want, so the logic depends on sliding start to maintain window size k, as shown by the window size column.

Visual Quiz - 3 Questions

Look at the execution_table, what is the window elements at Step 7?

A [2, 5, 8]

B [3, 2, 5]

C [5, 8, 7]

D [1, 3, 2]

💡 Hint

Check the 'Window Elements' column at Step 7 in the execution_table.

At which step does the window size first reach k=3?

A Step 2

B Step 4

C Step 3

D Step 1

💡 Hint

Look at the 'Window Size' column and find when it first equals 3.

If we do not slide the start pointer after printing, what will happen to the window size?

A It will decrease

B It will increase beyond k

C It will stay the same

D It will reset to zero

💡 Hint

Refer to the 'window size' changes in variable_tracker and key_moments about sliding start pointer.

Concept Snapshot

Sliding Window on Arrays:
- Use two pointers: start and end
- Expand end to grow window
- When window size == k, process window
- Slide start to move window forward
- Repeat until end reaches array end

Full Transcript

Sliding window on arrays uses two pointers to create a moving window of fixed size k. We start both pointers at zero. We move the end pointer forward to expand the window. When the window size reaches k, we process the current window elements. Then we slide the start pointer forward to shrink the window from the left, allowing the window to move forward. This repeats until the end pointer reaches the end of the array. This technique helps efficiently process all subarrays of size k without reprocessing the entire array each time.

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