Sliding Window on Arrays in DSA Javascript - Execution Trace

Concept Flow - Sliding Window on Arrays

Start: window at beginning

↓

Calculate window sum or value

↓

Move window right by 1

↓

Update sum by removing left, adding right

↓

Check if end reached?

No→Repeat

Yes↓

Done

The sliding window moves across the array, updating the sum or value by removing the left element and adding the new right element, until the window reaches the end.

Execution Sample

DSA Javascript

const arr = [1, 3, 2, 6, -1, 4, 1, 8, 2];
const k = 5;
let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += arr[i];
for (let i = k; i < arr.length; i++) {
  windowSum += arr[i] - arr[i - k];
}

Calculates the sum of every subarray of size k=5 by sliding the window across the array.

Execution Table

Step	Operation	Window Indices	Window Elements	Window Sum	Action
1	Initialize window sum	[0..4]	[1, 3, 2, 6, -1]	11	Sum first 5 elements
2	Slide window right by 1	[1..5]	[3, 2, 6, -1, 4]	14	Add arr[5]=4, remove arr[0]=1
3	Slide window right by 1	[2..6]	[2, 6, -1, 4, 1]	12	Add arr[6]=1, remove arr[1]=3
4	Slide window right by 1	[3..7]	[6, -1, 4, 1, 8]	18	Add arr[7]=8, remove arr[2]=2
5	Slide window right by 1	[4..8]	[-1, 4, 1, 8, 2]	14	Add arr[8]=2, remove arr[3]=6
6	End reached	-	-	-	Window reached end of array

💡 Window has slid through all possible positions; no more windows of size 5.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
windowSum	0	11	14	12	18	14	14
windowStart	0	0	1	2	3	4	4
windowEnd	4	4	5	6	7	8	8

Key Moments - 3 Insights

Why do we subtract arr[i - k] when sliding the window?

Because when the window moves right, the leftmost element leaves the window, so we remove its value from the sum to keep the window sum correct (see steps 2-5 in execution_table).

Why do we first sum the first k elements before sliding?

We need the initial sum of the first window to start sliding. Without it, we can't update the sum correctly when moving the window (see step 1 in execution_table).

What happens if the window size k is larger than the array length?

The window cannot slide because it doesn't fit. The code should handle this case separately to avoid errors or no operation (not shown in this example).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the window sum?

A 14

B 18

C 12

D 11

💡 Hint

Check the 'Window Sum' column at Step 3 in the execution_table.

At which step does the window include the element 8?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Window Elements' column to find when 8 first appears.

If the window size k was 3 instead of 5, how would the initial window sum change?

A Sum of first 3 elements: 6

B Sum of first 5 elements: 11

C Sum of last 3 elements: 11

D Sum of entire array

💡 Hint

Initial sum is always the sum of the first k elements, so with k=3, sum arr[0..2].

Concept Snapshot

Sliding Window on Arrays:
- Move a fixed-size window across the array
- Calculate initial sum of first k elements
- Slide window by removing left element, adding next right element
- Update sum efficiently without full recalculation
- Repeat until window reaches array end

Full Transcript

Sliding window on arrays means moving a fixed-size window across the array to calculate sums or other values efficiently. First, sum the first k elements to get the initial window sum. Then, slide the window right by one position each time. When sliding, remove the leftmost element's value from the sum and add the new rightmost element's value. Repeat this until the window reaches the end of the array. This method avoids recalculating the sum from scratch each time, making it faster. The execution table shows each step with the window's indices, elements, and sum. Key moments clarify why we subtract the left element and why the initial sum is needed. The visual quiz tests understanding of window sums and positions. This technique is useful for problems involving subarrays or continuous segments.

Practice

1. What is the main purpose of the sliding window technique when working with arrays?

easy

A. To find the maximum element in the entire array

B. To sort the array elements in ascending order

C. To reverse the array elements in place

D. To efficiently process subarrays of fixed size without recomputing everything

Solution

1. Step 1: Understand the sliding window concept

   The sliding window technique moves a fixed-size window over the array to process subarrays efficiently.

2. Step 2: Compare with other options

   Sorting, reversing, or finding max in the entire array are different operations not related to sliding window.

3. Final Answer:

   To efficiently process subarrays of fixed size without recomputing everything -> Option D

4. Quick Check:

   Sliding window = efficient fixed-size subarray processing [OK]

Hint: Sliding window moves fixed-size subarray to save work [OK]

Common Mistakes:

• Confusing sliding window with sorting or reversing
• Thinking it processes the whole array at once
• Assuming it finds max without window size

2. Which of the following is the correct syntax to initialize a sliding window sum for the first k elements in JavaScript?

easy

A. let sum = arr.slice(0, k).reduce((a, b) => a + b, 0);

B. let sum = arr.reduce((a, b) => a + b, 0);

C. let sum = arr.slice(k).reduce((a, b) => a + b, 0);

D. let sum = arr.splice(0, k).reduce((a, b) => a + b, 0);

Solution

1. Step 1: Understand how to get first k elements

   Using arr.slice(0, k) extracts the first k elements without modifying the array.

2. Step 2: Sum the elements correctly

   Using reduce((a, b) => a + b, 0) sums all elements in the sliced array.

3. Final Answer:

   let sum = arr.slice(0, k).reduce((a, b) => a + b, 0); -> Option A

4. Quick Check:

   slice(0,k) + reduce sum = correct initialization [OK]

Hint: Use slice(0,k) to get first window, then reduce to sum [OK]

Common Mistakes:

• Using reduce on whole array instead of first k elements
• Using splice which modifies the original array
• Slicing from k to end instead of 0 to k

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

const arr = [1, 3, 2, 6, -1, 4, 1, 8, 2];
const k = 5;
let maxSum = 0;
let windowSum = 0;

// Initialize first window sum
for(let i = 0; i < k; i++) {
  windowSum += arr[i];
}
maxSum = windowSum;

// Slide the window
for(let i = k; i < arr.length; i++) {
  windowSum += arr[i] - arr[i - k];
  if(windowSum > maxSum) maxSum = windowSum;
}
console.log(maxSum);

medium

A. 18

B. 17

C. 16

D. 19

Solution

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

   Sum of [1,3,2,6,-1] = 1+3+2+6-1 = 11

2. Step 2: Slide window and update sums

   Next windows and sums:
   Remove 1, add 4: 11 - 1 + 4 = 14
   Remove 3, add 1: 14 - 3 + 1 = 12
   Remove 2, add 8: 12 - 2 + 8 = 18 (maxSum updated to 18)
   Remove 6, add 2: 18 - 6 + 2 = 14

3. Step 3: Find maxSum

   Max sum found is 18

4. Final Answer:

   18 -> Option A

5. Quick Check:

   Max sliding window sum = 18 [OK]

Hint: Update sum by subtracting left, adding right element [OK]

Common Mistakes:

• Not updating maxSum correctly
• Adding instead of subtracting old element
• Wrong initial sum calculation

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

function maxSlidingWindowSum(arr, k) {
  let maxSum = 0;
  let windowSum = 0;
  for(let i = 0; i <= k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;
  for(let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    if(windowSum > maxSum) maxSum = windowSum;
  }
  return maxSum;
}

medium

A. The subtraction in the second loop is incorrect

B. The first loop should run while i < k, not i <= k

C. maxSum should be initialized to Number.MIN_VALUE

D. The function does not handle empty arrays

Solution

1. Step 1: Check the first loop range

   The first loop runs from i = 0 to i <= k, which means it accesses arr[k], an out-of-bound index for window size k.

2. Step 2: Correct the loop condition

   The loop should run while i < k to sum exactly k elements starting from index 0.

3. Final Answer:

   The first loop should run while i < k, not i <= k -> Option B

4. Quick Check:

   Loop range for first window = i < k [OK]

Hint: Loop for first window sums exactly k elements: i < k [OK]

Common Mistakes:

• Using <= k causes out-of-bounds error
• Ignoring array length checks
• Incorrect initialization of maxSum

5. Given an array of integers and a number k, how would you find the length of the longest subarray with sum less than or equal to k using the sliding window technique?

hard

A. Calculate prefix sums and find max subarray sum using Kadane's algorithm

B. Sort the array and use binary search to find subarrays with sum ≤ k

C. Expand the window by moving right pointer and shrink from left when sum exceeds k, track max length

D. Use nested loops to check all subarrays and pick the longest with sum ≤ k

Solution

1. Step 1: Use two pointers to create a sliding window

   Start with both pointers at the beginning, expand right pointer to add elements to sum.

2. Step 2: Shrink window from left when sum exceeds k

   If sum > k, move left pointer forward to reduce sum until sum ≤ k again, tracking max window length.

3. Step 3: Track the maximum length of valid windows

   Keep updating max length whenever sum ≤ k during expansion and shrinking.

4. Final Answer:

   Expand the window by moving right pointer and shrink from left when sum exceeds k, track max length -> Option C

5. Quick Check:

   Sliding window with two pointers and sum check = Expand the window by moving right pointer and shrink from left when sum exceeds k, track max length [OK]

Hint: Move right to expand, left to shrink when sum > k [OK]

Common Mistakes:

• Using sorting or binary search which doesn't apply here
• Using nested loops causing O(n²) time
• Confusing Kadane's algorithm with sum limit problem