Sliding Window on Arrays in DSA Typescript

Mental Model

A sliding window moves over the 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 the window step by step to see different parts without lifting it off the fence.

Array: [1] [2] [3] [4] [5] [6] [7]
Window size 3:
[1] [2] [3] ↑window
Then slide right:
    [2] [3] [4] ↑window
Then slide right:
        [3] [4] [5] ↑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 (first 3 elements)

Window: [2, 1, 5], sum = 8

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

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

Window: [1, 5, 2], sum = 8 - 2 + 2 = 8

Why: Update sum efficiently without adding all elements again

Step 3: Slide window right by 1: remove leftmost (1), add next element (3)

Window: [5, 2, 3], sum = 8 - 1 + 3 = 10

Why: Keep track of new window sum to find max

Step 4: Slide window right by 1: remove leftmost (5), add next element (2)

Window: [2, 3, 2], sum = 10 - 5 + 2 = 7

Why: Check if this window sum is the new max

Result:

Maximum sum window: [5, 2, 3] with sum = 10

Annotated Code

DSA Typescript

class SlidingWindow {
  static maxSumSubarray(arr: number[], k: number): number {
    if (arr.length < k) return 0; // window size larger than array
    let maxSum = 0;
    let windowSum = 0;
    // sum first window
    for (let i = 0; i < k; i++) {
      windowSum += arr[i];
    }
    maxSum = windowSum;
    // slide window
    for (let i = k; i < arr.length; i++) {
      windowSum += arr[i] - arr[i - k];
      if (windowSum > maxSum) {
        maxSum = windowSum;
      }
    }
    return maxSum;
  }
}

// Driver code
const arr = [2, 1, 5, 2, 3, 2];
const k = 3;
console.log("Maximum sum of subarray of size 3:", SlidingWindow.maxSumSubarray(arr, k));

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

Calculate initial sum of the first window

for (let 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 subarray of size 3: 10

Complexity Analysis

Time: O(n) because we traverse the array once, updating the window sum in constant time each step

Space: O(1) because we use only a few variables to track sums and max, no extra arrays

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

window size larger than array length

Returns 0 because no valid window can be formed

DSA Typescript

if (arr.length < k) return 0;

window size equals array length

Returns sum of entire array as only one window exists

DSA Typescript

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

array with negative numbers

Still finds maximum sum window correctly by comparing sums

DSA Typescript

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

When to Use This Pattern

When you need to find something (sum, max, min) over all subarrays of fixed size, use sliding window to avoid repeated work and improve efficiency.

Common Mistakes

Mistake: Recalculating the sum of each window from scratch instead of updating it
Fix: Use the sliding window formula: add new element and subtract the element leaving the window

Mistake: Not handling the case when window size is larger than array length
Fix: Add a guard clause to return 0 or handle gracefully when k > arr.length

Summary

Finds max sum of any subarray of fixed size by moving a window over the array

Use when you want to efficiently compute values over all fixed-size subarrays

Keep track of the sum by adding new element and removing old element as window slides

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