Sliding Window Maximum Using Deque in DSA Typescript - Execution Trace

Concept Flow - Sliding Window Maximum Using Deque

Start with empty deque

↓

For each element in array

↓

Remove indices from deque back if their values < current element

↓

Add current index to deque back

↓

Remove front index if it is out of current window

↓

If window is formed, record value at deque front as max

↓

Repeat until end of array

↓

Return list of max values

We keep indexes of useful elements in a deque, removing smaller elements and outdated ones, to find max in each sliding window.

Execution Sample

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

This code finds the maximum value in each sliding window of size k using a deque to track indices.

Execution Table

Step	Operation	Current Index i	Deque Indices	Deque Values	Max Recorded	Visual State
1	Start	-	[]	[]	[]	[]
2	Process nums[0]=1	0	[0]	[1]	-	[1]
3	Process nums[1]=3, pop 0 since 1<3	1	[1]	[3]	-	[3]
4	Process nums[2]=1, push 2	2	[1,2]	[3,1]	-	[3,1]
5	Process nums[3]=2, pop 2 since 1<2, push 3	3	[1,3]	[3,2]	3	[3,2]
6	Remove front if out of window (i=3,k=3), front=1 in window	3	[1,3]	[3,2]	3	[3,2]
7	Process nums[4]=0, push 4	4	[1,3,4]	[3,2,0]	3	[3,2,0]
8	Remove front if out of window (i=4,k=3), front=1 out (1<=4-3=1), remove 1	4	[3,4]	[2,0]	3,2	[2,0]
9	Process nums[5]=5, pop 4 and 3 since 0<5 and 2<5, push 5	5	[5]	[5]	3,2	[5]
10	Remove front if out of window (i=5,k=3), front=5 in window	5	[5]	[5]	3,2,5	[5]
11	Process nums[6]=1, push 6	6	[5,6]	[5,1]	3,2,5	[5,1]
12	Remove front if out of window (i=6,k=3), front=5 in window	6	[5,6]	[5,1]	3,2,5	[5,1]
13	Process nums[7]=2, pop 6 since 1<2, push 7	7	[5,7]	[5,2]	3,2,5	[5,2]
14	Remove front if out of window (i=7,k=3), front=5 out (5<=7-3=4), remove 5	7	[7]	[2]	3,2,5,2	[2]
15	Process nums[8]=3, pop 7 since 2<3, push 8	8	[8]	[3]	3,2,5,2	[3]
16	Remove front if out of window (i=8,k=3), front=8 in window	8	[8]	[3]	3,2,5,2,3	[3]
17	Process nums[9]=4, pop 8 since 3<4, push 9	9	[9]	[4]	3,2,5,2,3	[4]
18	Remove front if out of window (i=9,k=3), front=9 in window	9	[9]	[4]	3,2,5,2,3,4	[4]
19	End of array	-	[9]	[4]	3,2,5,2,3,4	[4]

💡 Reached end of array, all sliding window maximums recorded.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	After Step 15	After Step 17	Final
deque	[]	[0]	[1]	[1,2]	[1,3]	[1,3,4]	[5]	[5,6]	[5,7]	[8]	[9]	[9]
result	[]	[]	[]	[]	[3]	[3,2]	[3,2]	[3,2,5]	[3,2,5]	[3,2,5,2]	[3,2,5,2,3]	[3,2,5,2,3,4]
i	-	0	1	2	3	4	5	6	7	8	9	-

Key Moments - 3 Insights

Why do we remove indices from the back of the deque when their values are smaller than the current element?

Because smaller elements cannot be the maximum if a bigger element comes after them in the window. This is shown in steps 3, 5, 9, 13, 15, and 17 where popping happens to keep only useful candidates.

Why do we remove the front index if it is out of the current window?

The front index represents the maximum candidate for the current window. If it is outside the window (older than i-k), it must be removed to keep the deque valid. This happens in steps 8, 14, and others.

Why do we push indices instead of values into the deque?

Indices help us know if elements are inside the current window and allow us to compare values easily. This is clear in the variable tracker and execution table where deque stores indices, and values are accessed via nums[deque[i]].

Visual Quiz - 3 Questions

Look at the execution table at step 9. What is the state of the deque indices?

A [5]

B [3,4]

C [1,3,4]

D [5,6]

💡 Hint

Check the 'Deque Indices' column at step 9 in the execution table.

At which step does the first maximum value get recorded in the result array?

A Step 2

B Step 5

C Step 7

D Step 10

💡 Hint

Look at the 'Max Recorded' column to see when the first value appears.

If the window size k was increased, how would the 'Remove front if out of window' operation change?

A It would remove elements more often

B It would remove elements less often

C It would not remove any elements

D It would remove elements at the same frequency

💡 Hint

Consider how the condition 'deque[0] <= i - k' depends on k in the code and execution table.

Concept Snapshot

Sliding Window Maximum Using Deque:
- Use a deque to store indices of elements.
- Remove smaller elements from back before adding new.
- Remove front if out of current window.
- Front of deque is max for current window.
- Time complexity: O(n) due to each element added/removed once.

Full Transcript

This visualization shows how to find the maximum in each sliding window of size k in an array using a deque. We keep indices of useful elements in the deque, removing smaller elements from the back to maintain candidates for maximum. We also remove the front index if it falls out of the current window. At each step, when the window is fully formed, we record the value at the front of the deque as the maximum. The execution table tracks the deque indices, their values, and the maximums recorded step-by-step. The variable tracker shows how the deque and result arrays change after each operation. Key moments clarify why we remove elements from the deque and why indices are stored instead of values. The quiz tests understanding of the deque state and operations at specific steps. This method efficiently finds sliding window maximums in 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