Sliding Window on Arrays in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the sliding window technique in arrays?

It is a method to create a 'window' of elements that moves through the array to solve problems efficiently by avoiding repeated work.

intermediate

How does the sliding window improve performance compared to a nested loop?

It reduces time complexity by reusing previous computations instead of recalculating sums or counts for every new window, often changing O(n²) to O(n).

beginner

In a fixed-size sliding window, what happens when the window moves forward?

The element leaving the window is removed from the current calculation, and the new element entering the window is added.

intermediate

What is the difference between fixed-size and variable-size sliding windows?

Fixed-size windows have a constant length, while variable-size windows can grow or shrink based on conditions like sums or counts.

beginner

Give a real-life example to explain the sliding window concept.

Imagine looking through a small window on a moving train to see a few trees at a time. As the train moves, the window shows new trees while old ones disappear, similar to how the sliding window moves over an array.

What does the sliding window technique help to avoid in array problems?

A Using extra memory for each element

B Sorting the array multiple times

C Repeated calculations for overlapping parts

D Ignoring edge cases

Sliding window avoids recalculating values for parts of the array that overlap between windows.

Which of these problems is best suited for a sliding window approach?

A Reversing an array

B Sorting an array

C Finding duplicates in an array

D Finding the maximum sum of any subarray of size k

Sliding window efficiently finds sums or other aggregates over fixed-size subarrays.

In a sliding window of size 3, if the current window is [2, 5, 7], what is the next window after sliding one step?

A [5, 7, next element]

B [2, 5, next element]

C [7, next element, next element]

D [2, 7, next element]

The window moves forward by removing the first element and adding the next element.

What is the typical time complexity of a sliding window solution for fixed-size windows?

A O(n²)

B O(n)

C O(n log n)

D O(1)

Sliding window solutions usually run in linear time by processing each element once.

Which data structure is commonly used to implement variable-size sliding windows?

A Queue or deque

B Hash map only

C Binary tree

D Stack

Queues or deques help efficiently add and remove elements from both ends for variable-size windows.

Explain how the sliding window technique works with a fixed window size on an array.

Think about how you keep track of the sum or count as the window moves.

Describe a scenario where a variable-size sliding window is useful and how it adjusts its size.

Consider problems where the window changes size to meet a condition.

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