Sliding Window Maximum Using Deque in DSA Javascript

Mental Model

Keep track of the largest values in a window using a special list that quickly removes smaller values.

Analogy: Imagine a line of people waiting to buy tickets, but only the tallest people stay in line because shorter ones get blocked and leave. The tallest person at the front is always the biggest in the group.

Array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size k=4
Deque stores indexes of elements in decreasing order of values
Deque: front -> [indexes of biggest elements] -> back
Example:
Deque: [3, 4, 6] means values: [4, 6, 8]

Dry Run Walkthrough

Input: array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56], window size k=4

Goal: Find the maximum value in every window of size 4 as we slide from left to right

Step 1: Add index 0 (value 2) to deque

Deque: [0] (values: [2])

Why: Start with first element, deque empty so just add it

Step 2: Add index 1 (value 1) to deque after 0 because 1 < 2

Deque: [0, 1] (values: [2, 1])

Why: Keep indexes of elements in decreasing order, 1 is smaller so stays behind 2

Step 3: Add index 2 (value 3), remove indexes with smaller values (1 and 0) from back

Deque: [2] (values: [3])

Why: 3 is bigger than 1 and 2, so remove them to keep deque decreasing

Step 4: Add index 3 (value 4), remove index 2 (value 3) from back

Deque: [3] (values: [4])

Why: 4 is bigger than 3, so remove smaller from back

Step 5: Window reached size 4, max is value at front index 3 (4)

Output: [4]

Why: Front of deque always has max for current window

Step 6: Slide window: remove index 0 if out of window (0 < 1), no removal needed

Deque: [3] (values: [4])

Why: Index 0 is out of window, but not in deque now

Step 7: Add index 4 (value 6), remove index 3 (value 4) from back

Deque: [4] (values: [6])

Why: 6 is bigger than 4, remove smaller from back

Step 8: Window max is value at front index 4 (6)

Output: [4, 6]

Why: Max for current window is at front

Result:

Final output: [4, 6, 6, 8, 9, 10, 12, 56]

Annotated Code

DSA Javascript

class Deque {
  constructor() {
    this.items = [];
  }
  pushBack(val) {
    this.items.push(val);
  }
  popBack() {
    return this.items.pop();
  }
  popFront() {
    return this.items.shift();
  }
  front() {
    return this.items[0];
  }
  back() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
}

function slidingWindowMaximum(nums, k) {
  const deque = new Deque();
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // Remove indexes out of current window
    while (!deque.isEmpty() && deque.front() <= i - k) {
      deque.popFront();
    }

    // Remove smaller values from back
    while (!deque.isEmpty() && nums[deque.back()] < nums[i]) {
      deque.popBack();
    }

    // Add current index
    deque.pushBack(i);

    // Start adding max to result when window is full
    if (i >= k - 1) {
      result.push(nums[deque.front()]);
    }
  }

  return result;
}

// Driver code
const nums = [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56];
const k = 4;
const maxValues = slidingWindowMaximum(nums, k);
console.log(maxValues.join(", "));

while (!deque.isEmpty() && deque.front() <= i - k) { deque.popFront(); }

Remove indexes that are out of the current window from front

while (!deque.isEmpty() && nums[deque.back()] < nums[i]) { deque.popBack(); }

Remove smaller values from back to keep deque decreasing

deque.pushBack(i);

Add current index to deque

if (i >= k - 1) { result.push(nums[deque.front()]); }

Add max value for current window to result

Output

4, 6, 6, 8, 9, 10, 12, 56

Complexity Analysis

Time: O(n) because each element is added and removed from deque at most once

Space: O(k) because deque stores indexes only for current window size

vs Alternative: Naive approach checks all k elements per window leading to O(n*k), deque method is much faster

Edge Cases

Empty array

Returns empty result array

DSA Javascript

for (let i = 0; i < nums.length; i++) { ... }

Window size k equals 1

Each element is max of its own window, returns original array

DSA Javascript

if (i >= k - 1) { result.push(nums[deque.front()]); }

Window size k equals array length

Returns single max value of entire array

DSA Javascript

while (!deque.isEmpty() && deque.front() <= i - k) { deque.popFront(); }

When to Use This Pattern

When you need to find max or min in every sliding window efficiently, use the deque pattern to maintain candidates in order.

Common Mistakes

Mistake: Not removing indexes that are out of the current window from the front of the deque
Fix: Add a check to pop from front when index is outside the window: while (!deque.isEmpty() && deque.front() <= i - k) { deque.popFront(); }

Mistake: Not removing smaller values from the back before adding new index
Fix: Before pushing new index, pop from back all indexes with smaller values to keep deque decreasing

Summary

Finds maximum values in each sliding window of size k efficiently using a deque.

Use when you need fast max/min queries over sliding windows in arrays.

Keep indexes of elements in a deque in decreasing order and remove outdated or smaller elements.

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