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

Time Complexity: Sliding Window Maximum Using Deque

O(n)

Understanding Time Complexity

We want to understand how the time needed changes when finding the maximum in each sliding window of an array using a deque.

How does the number of steps grow as the array and window size grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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 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 visited once, and each index is added and removed from the deque at most once.

How Execution Grows With Input

As the array size grows, the number of operations grows roughly in direct proportion.

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

Pattern observation: The operations grow linearly with input size, not more.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly with the number of elements in the 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. The total work is still proportional to n.

Interview Connect

Understanding this linear time solution shows you can optimize sliding window problems efficiently, a skill valued in many coding challenges.

Self-Check

What if we changed the data structure from a deque to a simple array for storing 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 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