Why Sliding Window Maximum Using Deque in DSA Typescript?

The Big Idea

Discover how to find the hottest day in every 3-day stretch without checking each day again and again!

The Scenario

Imagine you have a long list of daily temperatures, and you want to find the hottest day in every 3-day period. Doing this by checking each 3-day group one by one feels like repeating the same work over and over.

The Problem

Manually checking each group means looking at many overlapping days multiple times. This takes a lot of time and can easily cause mistakes, especially if the list is very long.

The Solution

The sliding window maximum with a deque helps by remembering useful days and quickly skipping the ones that can't be the hottest. It moves through the list just once, making the process fast and simple.

Before vs After

✗ Before

for (let i = 0; i <= arr.length - k; i++) {
  let max = arr[i];
  for (let j = i + 1; j < i + k; j++) {
    if (arr[j] > max) max = arr[j];
  }
  console.log(max);
}

✓ After

const deque: number[] = [];
for (let i = 0; i < arr.length; i++) {
  while (deque.length && arr[deque[deque.length - 1]] <= arr[i]) deque.pop();
  deque.push(i);
  if (deque[0] === i - k) deque.shift();
  if (i >= k - 1) console.log(arr[deque[0]]);
}

What It Enables

This method lets you find maximum values in moving windows quickly, even for very large lists, without repeating work.

Real Life Example

Stock traders use this to find the highest stock price in the last 10 days as new prices come in every day, helping them make fast decisions.

Key Takeaways

Manual checking repeats work and is slow.

Deque keeps track of useful candidates efficiently.

Sliding window maximum runs in fast linear time.

Practice

1. What is the main purpose of using a deque in the Sliding Window Maximum algorithm?

easy

A. To reverse the array elements

B. To store all elements of the array for quick access

C. To sort the entire array before processing

D. To keep track of indices of elements in the current window in decreasing order of their values

Solution

1. Step 1: Understand the role of deque in the algorithm

   The deque stores indices of elements in the current window, maintaining them in decreasing order of their values to quickly find the maximum.

2. Step 2: Eliminate incorrect options

   Options A, B, and C do not describe the deque's role in maintaining order or tracking maximums.

3. Final Answer:

   To keep track of indices of elements in the current window in decreasing order of their values -> Option D

4. Quick Check:

   Deque stores indices in decreasing order = D [OK]

Hint: Deque keeps max candidates in order for O(1) max retrieval [OK]

Common Mistakes:

• Thinking deque stores actual values instead of indices
• Assuming deque sorts the entire array
• Confusing deque with a stack or queue only

2. Which of the following TypeScript code snippets correctly initializes an empty deque using an array for the Sliding Window Maximum algorithm?

easy

A. const deque: number[] = [];

B. const deque = new Deque();

C. const deque = []; deque.push(null);

D. const deque: string[] = [];

Solution

1. Step 1: Identify correct deque initialization in TypeScript

   Using an array of numbers is the common way to simulate a deque for indices, so const deque: number[] = []; is correct.

2. Step 2: Check other options for errors

   A pushes null which is incorrect, B uses a non-existent Deque class by default, and D uses string array which is wrong for indices.

3. Final Answer:

   const deque: number[] = []; -> Option A

4. Quick Check:

   Array of numbers for deque = C [OK]

Hint: Use number array for indices, no built-in Deque in TypeScript [OK]

Common Mistakes:

• Using string array instead of number array
• Trying to use a Deque class without importing
• Pushing null or undefined initially

3. What is the output of the following TypeScript code snippet for sliding window maximum with window size 3?

function maxSlidingWindow(nums: number[], k: number): number[] {
  const deque: number[] = [];
  const result: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    deque.push(i);
    if (deque[0] === i - k) {
      deque.shift();
    }
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  return result;
}

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

medium

A. [1, 3, -1, -3, 5, 3]

B. [3, 3, 5, 5, 6, 7]

C. [3, -1, -3, 5, 3, 6]

D. [7, 6, 5, 3, -3, -1]

Solution

1. Step 1: Trace the sliding window maximum for each window

   Windows and their max values: [1,3,-1] -> 3 [3,-1,-3] -> 3 [-1,-3,5] -> 5 [-3,5,3] -> 5 [5,3,6] -> 6 [3,6,7] -> 7

2. Step 2: Confirm the output array matches these max values

   The output array is [3, 3, 5, 5, 6, 7], which matches.

3. Final Answer:

   [3, 3, 5, 5, 6, 7] -> Option B

4. Quick Check:

   Sliding window max = [3,3,5,5,6,7] [OK]

Hint: Check max of each window manually to verify output [OK]

Common Mistakes:

• Not removing indices outside the window
• Incorrectly popping from deque
• Mixing values and indices in deque

4. Identify the bug in the following Sliding Window Maximum code snippet and select the correct fix:

function maxSlidingWindow(nums: number[], k: number): number[] {
  const deque: number[] = [];
  const result: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }
    deque.push(i);
    if (deque[0] <= i - k) {
      deque.shift();
    }
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  return result;
}

medium

A. Change condition to 'nums[deque[deque.length - 1]] <= nums[i]' in while loop

B. Change 'deque[0] <= i - k' to 'deque[0] < i - k' in if condition

C. Remove the if condition that shifts deque

D. Change 'deque.push(i)' to 'deque.unshift(i)'

Solution

1. Step 1: Analyze the while loop condition

   The condition 'nums[deque[deque.length - 1]] < nums[i]' does not pop elements equal to nums[i], keeping redundant candidates. It should use '<=' for strictly decreasing order.

2. Step 2: Check other options

   B would fail to remove exactly expired indices, C removes necessary logic, D reverses order incorrectly.

3. Final Answer:

   Change condition to 'nums[deque[deque.length - 1]] <= nums[i]' in while loop -> Option A

4. Quick Check:

   <= in while removes equals too [OK]

Hint: Use <= in while loop to remove equal values [OK]

Common Mistakes:

• Using < instead of <= in while loop
• Wrong fix changing shift condition to <
• Using unshift instead of push

5. Given an array nums = [4, 2, 12, 3, 8, 7, 9] and window size k = 4, what is the sliding window maximum output if the algorithm is modified to return the indices of maximum elements instead of values?

medium

A. [3, 4, 5, 6]

B. [0, 2, 4, 5]

C. [2, 2, 2, 6]

D. [2, 3, 4, 6]

Solution

1. Step 1: Find max values and their indices for each window of size 4

   Windows and max indices: [4,2,12,3] (0-3) -> 2 (12) [2,12,3,8] (1-4) -> 2 (12) [12,3,8,7] (2-5) -> 2 (12) [3,8,7,9] (3-6) -> 6 (9)

2. Step 2: Collect indices of max elements

   The indices are [2, 2, 2, 6].

3. Final Answer:

   [2, 2, 2, 6] -> Option C

4. Quick Check:

   Max indices per window = [2,2,2,6] [OK]

Hint: Track max element indices per window, not just values [OK]

Common Mistakes:

• Returning values instead of indices
• Mixing up indices when max repeats
• Not updating max index when window slides