Sliding Window Maximum Using Deque in DSA Javascript - Execution Trace

Concept Flow - Sliding Window Maximum Using Deque

Start

↓

Initialize deque as empty

↓

For each element in array

↓

Remove indices from deque back if current element > elements at those indices

↓

Add current index to deque back

↓

Remove front index if it is out of current window

↓

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

↓

Repeat until end of array

↓

Return list of max values

We slide a window over the array, keep indices of useful elements in a deque, and update max for each window.

Execution Sample

DSA Javascript

function maxSlidingWindow(nums, k) {
  const deque = [];
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && nums[i] >= nums[deque[deque.length - 1]]) 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 in each sliding window of size k using a deque to track indices of max candidates.

Execution Table

Step	Operation	Current Index (i)	Deque Indices	Deque Values	Window Max	Visual State
1	Start with empty deque	-	[]	[]	-	[]
2	Process element 1	0	[0]	[1]	-	[1]
3	Process element 3, pop 0 because 3 > 1	1	[1]	[3]	-	[3]
4	Process element -1, add index 2	2	[1,2]	[3,-1]	-	[3,-1]
5	Window formed (i=2), max is nums[1]=3	2	[1,2]	[3,-1]	3	[3,-1]
6	Process element -3, add index 3	3	[1,2,3]	[3,-1,-3]	3	[3,-1,-3]
7	Window formed (i=3), max is nums[1]=3	3	[1,2,3]	[3,-1,-3]	3	[3,-1,-3]
8	Process element 5, pop 3 and 2 and 1 because 5 > -3,-1,3	4	[4]	[5]	3	[5]
9	Remove index 1 (out of window)	4	[4]	[5]	5	[5]
10	Window formed (i=4), max is nums[4]=5	4	[4]	[5]	5	[5]
11	Process element 3, add index 5	5	[4,5]	[5,3]	5	[5,3]
12	Window formed (i=5), max is nums[4]=5	5	[4,5]	[5,3]	5	[5,3]
13	Process element 6, pop 5 and 4 because 6 > 3,5	6	[6]	[6]	5	[6]
14	Remove index 4 (out of window)	6	[6]	[6]	6	[6]
15	Window formed (i=6), max is nums[6]=6	6	[6]	[6]	6	[6]
16	Process element 7, pop 6 because 7 > 6	7	[7]	[7]	6	[7]
17	Remove index 5 (out of window)	7	[7]	[7]	7	[7]
18	Window formed (i=7), max is nums[7]=7	7	[7]	[7]	7	[7]
19	End of array	-	[7]	[7]	-	[7]

💡 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 8	After Step 13	After Step 16	Final
deque	[]	[0]	[1]	[1,2]	[1,2]	[4]	[6]	[7]	[7]
result	[]	[]	[]	[3]	[3,3]	[3,3,5]	[3,3,5,6]	[3,3,5,6,7]	[3,3,5,6,7]
i	-	0	1	2	2	4	6	7	7

Key Moments - 3 Insights

Why do we remove indices from the back of the deque when current element is greater?

Because those elements can never be maximum in the current or future windows if a bigger element comes later. See steps 3 and 8 where smaller elements are popped before adding a bigger one.

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

Because the front index represents the maximum candidate for the window, but if it is outside the window range, it cannot be maximum anymore. See step 9 and 14 where front indices are removed when out of window.

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

Indices help us know if elements are inside the current window and also allow us to compare values in the original array. This is shown in the 'Deque Indices' and 'Deque Values' columns in the execution table.

Visual Quiz - 3 Questions

Look at the execution table at step 8. What happens to the deque?

A Indices 3, 2, and 1 are popped before adding index 4

B Index 4 is popped before adding index 3

C Deque remains unchanged

D Only index 1 is popped

💡 Hint

Check the 'Operation' and 'Deque Indices' columns at step 8 in the execution table.

At which step does the first window maximum get recorded?

A Step 2

B Step 5

C Step 7

D Step 10

💡 Hint

Look for the first step where 'Window Max' column has a value in the execution table.

If the window size k was increased, how would the variable 'result' change in the variable tracker?

A It would remain the same

B It would have more elements

C It would have fewer elements

D It would be empty

💡 Hint

Consider how many windows fit in the array when k changes, and check the 'result' row in variable tracker.

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 window.
- Front of deque is max for current window.
- Time complexity: O(n) because each element is added and removed once.

Full Transcript

This visualization shows how to find the maximum in each sliding window of size k using a deque. We keep indices of useful elements in the deque, removing smaller elements from the back when a bigger element arrives. We also remove the front index if it goes out of the current window. The front of the deque always holds the index of the maximum element for the current window. The execution table traces each step, showing how the deque changes and when maximums are recorded. The variable tracker shows how the deque and result array evolve. Key moments clarify why we remove elements and why indices are stored. The quiz tests understanding of these steps. This method is efficient with O(n) time complexity.

Practice

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

easy

A. To sort the entire array before processing

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

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

D. To reverse the array elements

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: Why other options are incorrect

   To store all elements of the array for quick access is incorrect because deque does not store all elements, only relevant indices. To sort the entire array before processing and D do not relate to the sliding window maximum logic.

3. Final Answer:

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

4. Quick Check:

   Deque stores indices in decreasing order for max [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 without order

2. Which of the following is the correct syntax to initialize an empty deque in JavaScript for the Sliding Window Maximum algorithm?

easy

A. const deque = new ArrayDeque();

B. const deque = new Deque();

C. const deque = new Queue();

D. const deque = [];

Solution

1. Step 1: Identify JavaScript data structure for deque

   JavaScript does not have a built-in Deque class, so an empty array is used to simulate a deque.

2. Step 2: Why other options are invalid

   Options A, B, and D refer to classes not available in standard JavaScript.

3. Final Answer:

   const deque = []; -> Option D

4. Quick Check:

   Use array as deque in JS [OK]

Hint: Use array as deque in JavaScript [OK]

Common Mistakes:

• Trying to use non-existent Deque class
• Using Queue which lacks double-ended operations
• Confusing JavaScript with other languages' syntax

3. What is the output of the following code snippet?

function maxSlidingWindow(nums, k) {
  const deque = [];
  const result = [];
  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. [7, 6, 5, 3, -3, -1]

D. [3, 5, 6, 7]

Solution

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

   Windows of size 3 and their max values are: [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 result array matches the expected output

   The result array is [3, 3, 5, 5, 6, 7], matching [3, 3, 5, 5, 6, 7].

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: Track max in each window using deque indices [OK]

Common Mistakes:

• Not removing indices outside the window
• Pushing values instead of indices into deque
• Incorrectly updating the result array

4. Identify the bug in the following Sliding Window Maximum code snippet:

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

medium

A. The condition in the while loop should compare with the last element, not the first

B. The deque should store values, not indices

C. The if condition to remove out-of-window indices is missing

D. The result array is not being returned

Solution

1. Step 1: Analyze the while loop condition

   The while loop incorrectly compares nums[deque[0]] (front) with nums[i], but it should compare with nums[deque[deque.length - 1]] (back) to maintain decreasing order.

2. Step 2: Confirm other parts are correct

   The deque stores indices correctly, the out-of-window removal condition exists, and the result is returned properly.

3. Final Answer:

   The condition in the while loop should compare with the last element, not the first -> Option A

4. Quick Check:

   Compare with deque's last element in while loop [OK]

Hint: While loop must check deque's last element for correct order [OK]

Common Mistakes:

• Comparing with front instead of back in deque
• Storing values instead of indices in deque
• Forgetting to remove indices outside the window

5. Given an array nums = [4, 2, 12, 3, 8, 7, 9] and window size k = 4, what will be the output of the Sliding Window Maximum algorithm using a deque?

hard

A. [12, 12, 12, 9]

B. [4, 12, 8, 9]

C. [12, 3, 8, 7]

D. [4, 2, 12, 3]

Solution

1. Step 1: Identify each window and its maximum

   Windows of size 4 are: [4,2,12,3] max=12, [2,12,3,8] max=12, [12,3,8,7] max=12, [3,8,7,9] max=9.

2. Step 2: Collect the maximums in order

   The result array is [12, 12, 12, 9], matching [12, 12, 12, 9].

3. Final Answer:

   [12, 12, 12, 9] -> Option A

4. Quick Check:

   Max per window = [12,12,12,9] [OK]

Hint: Check max in each window by comparing edges with deque [OK]

Common Mistakes:

• Not sliding window correctly by one index
• Forgetting to remove old indices from deque
• Mixing values and indices in deque