Sliding Window Maximum Using Deque in DSA Typescript - Build from Scratch

Sliding Window Maximum Using Deque

📖 Scenario: Imagine you are analyzing the temperature readings of a city over several days. You want to find the highest temperature recorded in every 3-day window to understand heat trends.

🎯 Goal: Build a program that uses a deque (double-ended queue) to efficiently find the maximum temperature in every sliding window of size 3.

📋 What You'll Learn

Create an array called temperatures with the exact values: [4, 2, 12, 11, 8, 7, 15]

Create a variable called windowSize and set it to 3

Implement the sliding window maximum logic using a deque to store indices

Print the resulting array of maximums for each window

💡 Why This Matters

🌍 Real World

Sliding window maximum is used in real-time data analysis like temperature monitoring, stock price analysis, and network traffic monitoring to quickly find maximum values in moving windows.

💼 Career

Understanding sliding window techniques and efficient data structures like deque is important for software engineers working on performance-critical applications, data streaming, and algorithm optimization.

1

Create the temperature data array

Create an array called temperatures with these exact values: [4, 2, 12, 11, 8, 7, 15]

DSA Typescript

# Create the temperatures array with the given values
// Your code here

Hint

Use const temperatures = [4, 2, 12, 11, 8, 7, 15]; to create the array.

2

Set the sliding window size

Create a variable called windowSize and set it to 3

DSA Typescript

const temperatures = [4, 2, 12, 11, 8, 7, 15];
// Create windowSize variable and set it to 3
// Your code here

Hint

Use const windowSize = 3; to set the window size.

3

Implement sliding window maximum using deque

Create a function called slidingWindowMax that takes nums and k as parameters. Use a deque (array used as double-ended queue) to store indices. Loop through nums using i as index. Remove indices from the back of the deque while the current number is greater than or equal to the number at those indices. Remove the front index if it is out of the current window. Add the current index to the back of the deque. Starting from i >= k - 1, push the number at the front index of the deque to the result array. Return the result array.

DSA Typescript

const temperatures = [4, 2, 12, 11, 8, 7, 15];
const windowSize = 3;
// Implement slidingWindowMax function using deque
// Your code here

Hint

Use a for loop with index i. Use deque.pop() to remove smaller elements from the back. Use deque.shift() to remove indices out of the window from the front. Push i to the deque. Add nums[deque[0]] to result when i >= k - 1.

4

Print the sliding window maximum results

Call slidingWindowMax with temperatures and windowSize. Store the result in maxTemperatures. Print maxTemperatures using console.log.

DSA Typescript

const temperatures = [4, 2, 12, 11, 8, 7, 15];
const windowSize = 3;

function slidingWindowMax(nums: number[], k: number): number[] {
    const deque: number[] = [];
    const result: number[] = [];

    for (let i = 0; i  0 && nums[i] >= nums[deque[deque.length - 1]]) {
            deque.pop();
        }

        if (deque.length > 0 && deque[0] = k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

// Call slidingWindowMax and print the result
// Your code here

Hint

Call slidingWindowMax(temperatures, windowSize) and print the result with console.log.

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