Sliding Window Maximum Using Deque in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sliding Window Maximum for a Simple Array

What is the output of the following TypeScript code that finds the maximum in each sliding window of size 3 using a deque?

DSA Typescript

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));

A [3, 3, 5, 5, 6, 7]

B [1, 3, -1, -3, 5, 3]

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

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

💡 Hint

Focus on how the deque stores indices of elements in decreasing order and removes indices out of the current window.

The deque keeps indices of elements in decreasing order of their values. For each window, the front of the deque is the index of the maximum element. The output array collects these maximums for each sliding window.

🧠 Conceptual

intermediate

Understanding Deque Behavior in Sliding Window Maximum

In the sliding window maximum algorithm using a deque, what is the main reason for removing elements from the back of the deque when a new element arrives?

A To remove elements that are smaller or equal to the new element, ensuring the deque stores indices of elements in decreasing order

B To keep the deque sorted in increasing order of values

C To remove elements that are outside the current window

D To maintain the deque size equal to the window size

💡 Hint

Think about how the deque helps quickly find the maximum in the current window.

Removing smaller or equal elements from the back ensures that the deque stores indices of elements in decreasing order of their values. This way, the front always holds the index of the maximum element.

❓ Predict Output

advanced

Output of Sliding Window Maximum with Negative and Repeated Numbers

What is the output of this TypeScript code for sliding window maximum with window size 4?

DSA Typescript

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([4, -2, -2, 5, 6, 5, 1, 7], 4));

A [4, 5, 6, 7, 7]

B [5, 6, 6, 7, 7]

C [5, 6, 5, 7, 7]

D [4, -2, 5, 6, 7]

💡 Hint

Trace the deque updates carefully for each window.

The maximums for windows of size 4 are: [4, -2, -2, 5], max is 5; [ -2, -2, 5, 6], max is 6; [ -2, 5, 6, 5], max is 6; [5, 6, 5, 1], max is 7; [6, 5, 1, 7], max is 7.

🔧 Debug

advanced

Identify the Error in Sliding Window Maximum Implementation

What error will this TypeScript code produce when run, and why?

DSA Typescript

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([2,1,3,4,6,3,8,9,10,12,56], 4));

A Runtime error: deque[0] is undefined when i < k

B No error, outputs correct sliding window maximum

C Incorrect output because the condition to remove out-of-window indices is wrong

D Syntax error due to missing colon or bracket

💡 Hint

Check the condition that removes indices out of the current window.

The condition 'deque[0] <= i - k' incorrectly removes indices that are still in the window. It should be 'deque[0] === i - k' to remove only the index that just moved out of the window.

🚀 Application

expert

Number of Maximum Elements Stored in Deque After Processing

After running the sliding window maximum algorithm with a deque on the array [10, 9, 8, 7, 6, 5, 4] with window size 3, how many elements remain in the deque at the end of the process?

A 0

B 3

C 7

D 1

💡 Hint

Consider how the deque stores indices of elements in decreasing order and removes smaller elements.

Since the array is strictly decreasing, each new element is smaller than the previous, so no elements are removed from the back. The deque holds indices of the last k elements. But as the window slides, indices out of the window are removed from the front. At the end, only the index of the last element remains.

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