Sliding Window Maximum Using Deque in DSA Javascript - Time & Space Complexity

Time Complexity: Sliding Window Maximum Using Deque

O(n)

Understanding Time Complexity

We want to know how fast we can find the maximum in every sliding window of an array.

How does the time needed grow as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity 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;
}
    

This code finds the maximum value in every window of size k as it slides over the array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop over the array elements.
• How many times: Each element is added and removed from the deque at most once.

How Execution Grows With Input

As the array size grows, each element is processed a limited number of times.

Input Size (n)	Approx. Operations
10	About 20 (each element pushed and popped once)
100	About 200
1000	About 2000

Pattern observation: The operations grow roughly in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find all sliding window maximums grows directly with the size of the input array.

Common Mistake

[X] Wrong: "Because of the nested while loop, the time complexity is O(n*k)."

[OK] Correct: Each element is pushed and popped at most once, so the inner loop does not run for every element repeatedly, keeping the total operations linear.

Interview Connect

Understanding this efficient approach shows you can optimize from a simple but slow method to a smart, fast one using the right data structure.

Self-Check

"What if we used a simple array instead of a deque to store indices? How would the time complexity change?"

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