Sliding Window on Arrays in DSA Typescript - Execution Trace

Concept Flow - Sliding Window on Arrays

Start

↓

Initialize window pointers: start=0, end=0

↓

Expand window by moving end pointer

↓

Check window size or condition

↓

Process window

↓

Slide window by moving start pointer

↓

Repeat until end reaches array end

↓

End

Start with two pointers defining a window on the array. Expand the window by moving the end pointer, check conditions, process the window, then slide the window by moving the start pointer. Repeat until the window covers the array.

Execution Sample

DSA Typescript

const arr = [2, 1, 5, 2, 3, 2];
const k = 3;
let maxSum = 0;
let windowSum = 0;
let windowStart = 0;
for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
  windowSum += arr[windowEnd];
  if (windowEnd >= k - 1) {
    maxSum = Math.max(maxSum, windowSum);
    windowSum -= arr[windowStart];
    windowStart++;
  }
}

Find the maximum sum of any contiguous subarray of size k using a sliding window.

Execution Table

Step	Operation	Window Start	Window End	Window Elements	Window Sum	Max Sum	Pointer Changes	Visual State
1	Add arr[0]=2	0	0	[2]	2	0	windowEnd=0	2 -> null
2	Add arr[1]=1	0	1	[2,1]	3	0	windowEnd=1	2 -> 1 -> null
3	Add arr[2]=5	0	2	[2,1,5]	8	8	windowEnd=2	2 -> 1 -> 5 -> null
4	Slide window: remove arr[0]=2	1	2	[1,5]	6	8	windowStart=1	1 -> 5 -> null
5	Add arr[3]=2	1	3	[1,5,2]	8	8	windowEnd=3	1 -> 5 -> 2 -> null
6	Slide window: remove arr[1]=1	2	3	[5,2]	7	8	windowStart=2	5 -> 2 -> null
7	Add arr[4]=3	2	4	[5,2,3]	10	10	windowEnd=4	5 -> 2 -> 3 -> null
8	Slide window: remove arr[2]=5	3	4	[2,3]	5	10	windowStart=3	2 -> 3 -> null
9	Add arr[5]=2	3	5	[2,3,2]	7	10	windowEnd=5	2 -> 3 -> 2 -> null
10	Slide window: remove arr[3]=2	4	5	[3,2]	5	10	windowStart=4	3 -> 2 -> null
11	End: windowEnd=6 (array length)	4	5	[3,2]	5	10	No change	3 -> 2 -> null

💡 windowEnd reached array length 6, loop ends

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
windowStart	0	0	0	1	1	2	2	3	3	4	4	4
windowEnd	0	1	2	2	3	3	4	4	5	5	6	6
windowSum	0	2	3	8	6	8	7	10	5	7	5	5
maxSum	0	0	0	8	8	8	8	10	10	10	10	10

Key Moments - 3 Insights

Why do we start sliding the window only after windowEnd reaches k-1?

Because before windowEnd reaches k-1, the window size is smaller than k, so we cannot process a full window yet. See execution_table rows 1-3 where windowEnd < 2, windowSum accumulates but maxSum is not updated.

Why do we subtract arr[windowStart] when sliding the window?

Subtracting arr[windowStart] removes the element leaving the window to keep the windowSum accurate for the new window. See execution_table row 4 where arr[0]=2 is removed from windowSum.

How do windowStart and windowEnd pointers move relative to each other?

windowEnd always moves forward by one each iteration, expanding the window. windowStart moves forward only after the window reaches size k, sliding the window forward. See variable_tracker for pointer values.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the maxSum value?

A 8

B 7

C 10

D 6

💡 Hint

Check the 'Max Sum' column at step 7 in execution_table

At which step does the window first slide forward by removing an element?

A Step 3

B Step 4

C Step 5

D Step 2

💡 Hint

Look for the first 'Slide window' operation in execution_table

If k was changed to 2, how would the window size check in execution_table change?

A Sliding starts after windowEnd >= 1

B Sliding starts after windowEnd >= 2

C Sliding starts after windowEnd >= 0

D Sliding never starts

💡 Hint

Sliding starts when windowEnd >= k-1, so with k=2, it starts at windowEnd=1

Concept Snapshot

Sliding Window on Arrays:
- Use two pointers (start, end) to define a window
- Expand window by moving end pointer
- When window size reaches k, process window
- Slide window by moving start pointer and adjusting sums
- Repeat until end reaches array end
- Efficient for fixed-size or condition-based subarray problems

Full Transcript

Sliding window technique uses two pointers to create a moving window over an array. We start both pointers at zero. We expand the window by moving the end pointer and adding elements to the window sum. Once the window size reaches the target size k, we process the window (e.g., update max sum). Then we slide the window forward by moving the start pointer and subtracting the element leaving the window from the sum. This repeats until the end pointer reaches the end of the array. This method avoids recomputing sums from scratch and is efficient for fixed-size subarray problems.

Practice

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

easy

A. To find the maximum element in the entire array

B. To sort the array in ascending order

C. To reverse the elements of the array

D. To efficiently process subarrays of fixed size without repeated work

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: Identify the purpose

   It avoids recalculating values for overlapping parts of subarrays, improving performance.

3. Final Answer:

   To efficiently process subarrays of fixed size without repeated work -> Option D

4. Quick Check:

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

Hint: Think of a moving window over array parts for efficiency [OK]

Common Mistakes:

• Confusing sliding window with sorting
• Thinking it reverses the array
• Assuming it finds max of whole array

2. Which of the following is the correct TypeScript syntax to start a sliding window loop for an array arr with window size k?

easy

A. for (let i = 0; i < arr.length; i += k)

B. for (let i = 0; i < arr.length + k; i++)

C. for (let i = 0; i <= arr.length - k; i++)

D. for (let i = 1; i <= arr.length - k; i++)

Solution

1. Step 1: Determine loop range for sliding window

   The window of size k must fit inside the array, so the last start index is arr.length - k.

2. Step 2: Check loop syntax correctness

   Loop from i = 0 up to and including arr.length - k ensures all windows are covered.

3. Final Answer:

   for (let i = 0; i <= arr.length - k; i++) -> Option C

4. Quick Check:

   Loop runs from 0 to arr.length - k inclusive [OK]

Hint: Loop until index allows full window inside array [OK]

Common Mistakes:

• Using < instead of <= causing last window to miss
• Starting loop at 1 instead of 0
• Incrementing by k skipping windows

3. What is the output of this TypeScript code?

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

for (let i = 0; i < k; i++) {
  windowSum += arr[i];
}
result.push(windowSum);

for (let i = k; i < arr.length; i++) {
  windowSum += arr[i] - arr[i - k];
  result.push(windowSum);
}

console.log(result);

medium

A. [11, 14, 12, 18, 14]

B. [11, 10, 12, 15, 13]

C. [11, 14, 17, 20, 23]

D. [11, 13, 15, 17, 19]

Solution

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

   1 + 3 + 2 + 6 + (-1) = 11. result = [11]

2. Step 2: Slide window and update sums

   i=5: 11 - 1 + 4 = 14
   i=6: 14 - 3 + 1 = 12
   i=7: 12 - 2 + 8 = 18
   i=8: 18 - 6 + 2 = 14
   result = [11, 14, 12, 18, 14]

3. Final Answer:

   [11, 14, 12, 18, 14] -> Option A

4. Quick Check:

   windowSum += arr[i] - arr[i - k] each slide [OK]

Hint: Add new element, subtract old element for each slide [OK]

Common Mistakes:

• Not subtracting the element leaving the window
• Incorrect initial sum calculation
• Off-by-one errors in loop indices

4. Identify the error in this sliding window code snippet and choose the fix:

const arr = [2, 1, 5, 1, 3, 2];
const k = 3;
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 = windowSum + arr[i] - arr[i + k];
  if (windowSum > maxSum) {
    maxSum = windowSum;
  }
}
console.log(maxSum);

medium

A. Initialize maxSum to Number.MIN_VALUE

B. Change arr[i + k] to arr[i - k] in the second loop

C. Change first loop to run from i = 1 to k

D. Add a check if i + k < arr.length before subtraction

Solution

1. Step 1: Analyze the sliding window update

   The window slides by removing the element leaving the window and adding the new element entering it. The element leaving is at index i - k, not i + k.

2. Step 2: Correct the subtraction index

   Change arr[i + k] to arr[i - k] to correctly remove the leftmost element of the previous window.

3. Final Answer:

   Change arr[i + k] to arr[i - k] in the second loop -> Option B

4. Quick Check:

   Subtract element leaving window at i-k [OK]

Hint: Subtract element at i-k, not i+k, when sliding window [OK]

Common Mistakes:

• Using wrong index for element leaving window
• Not initializing maxSum correctly
• Loop range errors

5. Given an array of integers, write a sliding window algorithm to find the maximum sum of any subarray of size k. Which approach below correctly implements this in TypeScript?

hard

A. Initialize sum of first k elements, then slide window adding new element and subtracting old, updating max sum each time

B. Sort the array and sum the first k elements

C. Use nested loops to sum every subarray of size k and track max sum

D. Add all elements and divide by k to get average, then multiply by k for max sum

Solution

1. Step 1: Understand the sliding window max sum approach

   Calculate sum of first k elements as initial window sum.

2. Step 2: Slide window across array

   For each new element, add it and subtract the element leaving the window, update max sum if current sum is higher.

3. Step 3: Avoid inefficient methods

   Sorting or nested loops are less efficient; averaging does not find max sum.

4. Final Answer:

   Initialize sum of first k elements, then slide window adding new element and subtracting old, updating max sum each time -> Option A

5. Quick Check:

   Sliding window updates sum and tracks max [OK]

Hint: Slide window, update sum and max in one pass [OK]

Common Mistakes:

• Using nested loops causing slow performance
• Sorting array which changes element order
• Calculating average instead of max sum