Sliding Window Maximum Using Deque in DSA Javascript - Deep Dive

Overview - Sliding Window Maximum Using Deque

What is it?

Sliding Window Maximum Using Deque is a technique to find the largest number in every fixed-size group of consecutive elements in a list. Imagine looking through a window that moves step-by-step over a row of numbers, and at each step, you want to know the biggest number inside that window. The deque (double-ended queue) helps keep track of candidates for the maximum efficiently, so you don't have to check all numbers every time the window moves.

Why it matters

Without this method, finding the maximum in each window would require checking every element inside the window repeatedly, which is slow for large lists. This technique speeds up the process to run much faster, making it practical for real-time data analysis, like monitoring stock prices or sensor readings. Without it, many applications would be too slow or inefficient to use.

Where it fits

Before learning this, you should understand arrays, queues, and basic loops. After this, you can explore other sliding window problems, like sums or minimums, and advanced data structures like segment trees or balanced trees for range queries.

Mental Model

Core Idea

Keep only useful elements in a special queue so the front always shows the current window's maximum without checking all elements.

Think of it like...

It's like keeping a line of tallest friends in order, where shorter friends behind taller ones leave the line because they can't be the tallest in future views.

Window moves over array:

Array: 2 1 3 4 6 3 8 9 10 12 56
Window size: 4

Deque stores indexes of elements in decreasing order of values:

Step 1: [2,1,3,4] -> Deque: 4 (index of 4)
Step 2: [1,3,4,6] -> Deque: 6 (index of 6)
Step 3: [3,4,6,3] -> Deque: 6
Step 4: [4,6,3,8] -> Deque: 8
Step 5: [6,3,8,9] -> Deque: 9
Step 6: [3,8,9,10] -> Deque: 10
Step 7: [8,9,10,12] -> Deque: 12
Step 8: [9,10,12,56] -> Deque: 56

At each step, front of deque is max in window.

Build-Up - 7 Steps

1

Foundation

Understanding the Sliding Window Concept

Concept: Learn what a sliding window is and how it moves over an array.

Imagine you have a list of numbers and a window size k. The window covers k numbers at a time, starting from the beginning. You move the window one step to the right each time, covering the next group of k numbers until you reach the end. For example, with array [2,1,3,4,6] and window size 3, the windows are [2,1,3], [1,3,4], [3,4,6].

Result

You get multiple overlapping groups of numbers, each of size k, sliding from left to right.

Understanding the sliding window is key because it defines the problem: processing overlapping groups efficiently.

2

Foundation

Brute Force Maximum in Each Window

Concept: Find the maximum by checking all elements inside each window.

For each window, look at all k elements and find the largest. For example, for [2,1,3], max is 3; for [1,3,4], max is 4; for [3,4,6], max is 6. This works but repeats work for overlapping parts.

Result

Output: [3,4,6] for the example above.

This method is simple but slow for large arrays because it repeats comparisons for overlapping elements.

3

Intermediate

Introducing Deque for Efficient Tracking

Concept: Use a double-ended queue to store indexes of elements that might be maximums.

A deque lets you add or remove elements from both ends quickly. We keep indexes of elements in the deque in decreasing order of their values. When a new element comes, remove smaller elements from the back because they can't be maximum if a bigger element is after them.

Result

Deque always holds candidates for maximum in order, front is current max index.

Using a deque reduces repeated comparisons by remembering only useful elements.

4

Intermediate

Sliding Window Maximum Algorithm Steps

🤔Before reading on: do you think the deque stores values or indexes? Commit to your answer.

Concept: Step-by-step process to maintain the deque and find maximums as the window slides.

1. Start with an empty deque. 2. For each element, remove indexes from the back if their values are less than current element. 3. Add current element's index to the back. 4. Remove front index if it is out of the current window. 5. The front of the deque is the max for the current window. 6. Repeat for all elements.

Result

Efficiently find maximum for each window in O(n) time.

Knowing the exact steps helps implement the algorithm correctly and efficiently.

5

Intermediate

Implementing Sliding Window Maximum in JavaScript

🤔Before reading on: do you think the code will use array methods or a custom deque class? Commit to your answer.

Concept: Write runnable JavaScript code using arrays as deque to solve the problem.

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; } // Example usage: console.log(maxSlidingWindow([2,1,3,4,6,3,8,9,10,12,56], 4));

Result

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

Seeing the full code connects the theory to practice and shows how to use arrays as deques in JavaScript.

6

Advanced

Time Complexity and Why It's O(n)

🤔Before reading on: do you think each element is processed once or multiple times in the deque? Commit to your answer.

Concept: Analyze why the algorithm runs in linear time despite nested loops.

Each element is added to the deque once and removed once. The inner while loop removes smaller elements but each removal corresponds to a unique element. So total operations are proportional to n, making the algorithm O(n).

Result

Algorithm runs efficiently even for large inputs.

Understanding this prevents confusion about nested loops and helps appreciate the efficiency.

7

Expert

Handling Edge Cases and Memory Optimization

🤔Before reading on: do you think the deque can grow larger than the window size? Commit to your answer.

Concept: Learn how to handle cases like empty arrays, window size 1, or very large inputs, and optimize memory use.

If the array is empty or k is 0, return empty. For k=1, max is each element itself. The deque never grows larger than k because old indexes are removed when out of window. This keeps memory use minimal. Also, careful with index checks to avoid errors.

Result

Robust code that works correctly in all cases and uses memory efficiently.

Knowing edge cases and memory behavior is crucial for production-ready code.

Under the Hood

The deque stores indexes of elements in decreasing order of their values. When a new element arrives, smaller elements at the back are removed because they cannot be maximum if a bigger element is after them. The front of the deque always holds the index of the maximum element for the current window. As the window slides, indexes that fall out of the window range are removed from the front. This process ensures each element is added and removed at most once, making the algorithm efficient.

Why designed this way?

This design avoids repeated scanning of the window by remembering only candidates that can be maximum. Alternatives like checking all elements each time are slow. Using a deque allows constant time insertions and deletions at both ends, perfectly fitting the sliding window's needs. This approach was chosen to optimize time complexity from O(n*k) to O(n).

Sliding Window Maximum Mechanism:

+----------------------------+
|          Array             |
|  [2,1,3,4,6,3,8,9,10,12,56]|
+----------------------------+
          ↓
+----------------------------+
|          Deque             |
|  Stores indexes of elements|
|  in decreasing order of    |
|  their values             |
+----------------------------+
          ↓
+----------------------------+
|  Front of deque = max index|
|  Remove indexes out of     |
|  window from front        |
|  Remove smaller elements   |
|  from back when new comes |
+----------------------------+

Myth Busters - 4 Common Misconceptions

Quick: Does the deque store the actual values or their indexes? Commit to one.

Common Belief: The deque stores the actual values of the elements in the window.

Reality: The deque stores indexes of elements, not the values themselves, to track their positions and know when they fall out of the window.

Why it matters: Storing values instead of indexes makes it impossible to know if an element is outside the current window, leading to incorrect maximums.

Quick: Is the time complexity O(n*k) or O(n)? Commit to your answer.

Common Belief: Because there is a nested loop, the algorithm runs in O(n*k) time.

Reality: Each element is added and removed from the deque at most once, so the total operations are O(n), making the algorithm linear time.

Why it matters: Misunderstanding complexity can lead to rejecting this efficient method and using slower brute force approaches.

Quick: Can the deque grow larger than the window size? Commit to yes or no.

Common Belief: The deque can grow larger than the window size because it stores all elements seen so far.

Reality: The deque size never exceeds the window size because indexes outside the window are removed from the front.

Why it matters: Thinking the deque grows unbounded can cause unnecessary worries about memory and prevent using this method.

Quick: Does removing smaller elements from the back risk losing the maximum? Commit to yes or no.

Common Belief: Removing smaller elements from the back might remove the maximum element accidentally.

Reality: Only smaller elements behind a bigger one are removed; the maximum is always at the front and never removed prematurely.

Why it matters: Misunderstanding this can cause incorrect implementations that lose track of the maximum.

Expert Zone

1

The deque maintains a strictly decreasing sequence of values by indexes, which ensures the maximum is always at the front without scanning.

2

When multiple elements have the same value, the deque keeps their indexes in order, ensuring correct maximums even with duplicates.

3

The algorithm's linear time depends on each element being pushed and popped once; careless implementation can break this and cause worse performance.

When NOT to use

This method is ideal for fixed-size sliding windows. For variable-size windows or complex queries like sum or median, other data structures like balanced trees or heaps are better. Also, if the input is static and many queries exist, segment trees or sparse tables may be more efficient.

Production Patterns

Used in real-time monitoring systems to track maximum sensor readings, in finance to find peak stock prices over intervals, and in competitive programming for efficient range maximum queries. Often combined with other sliding window techniques for complex data stream analysis.

Connections

Monotonic Queue

Sliding Window Maximum uses a monotonic queue pattern to maintain order.

Understanding monotonic queues helps grasp how the deque keeps elements sorted to quickly find maximums.

Two Pointer Technique

Both involve moving pointers/windows over data to solve problems efficiently.

Knowing two pointers clarifies how sliding windows move and why we remove elements that fall out of range.

Real-Time Signal Processing

Sliding window maximum is used to find peaks in streaming data signals.

Recognizing this connection shows how algorithms solve practical problems like noise filtering and peak detection.

Common Pitfalls

#1 Removing elements from the front of the deque without checking if they are out of the current window.

Wrong approach:

if (deque[0] < i - k + 1) { deque.shift(); } // wrong because it uses < instead of ===

Correct approach:

if (deque[0] === i - k) { deque.shift(); }

Root cause:

Confusing the window boundary condition causes premature or late removal of elements, leading to wrong maximums.

#2 Comparing values directly without using indexes, causing incorrect removals.

Wrong approach:

while (deque.length && deque[deque.length - 1] < nums[i]) { deque.pop(); } // wrong because deque stores indexes, not values

Correct approach:

while (deque.length && nums[deque[deque.length - 1]] < nums[i]) { deque.pop(); }

Root cause:

Not realizing the deque stores indexes leads to comparing indexes instead of values.

#3 Not pushing the current index into the deque after removals.

Wrong approach:

while (deque.length && nums[deque[deque.length - 1]] < nums[i]) { deque.pop(); } // missing deque.push(i)

Correct approach:

while (deque.length && nums[deque[deque.length - 1]] < nums[i]) { deque.pop(); } deque.push(i);

Root cause:

Forgetting to add the current element means losing track of potential maximums.

Key Takeaways

Sliding Window Maximum Using Deque efficiently finds maximums in overlapping groups by storing only useful candidates in a special queue.

The deque stores indexes in decreasing order of values, ensuring the front is always the current window's maximum.

Each element is added and removed from the deque at most once, making the algorithm run in linear time.

Careful handling of window boundaries and deque operations is essential for correct and efficient implementation.

This technique is widely used in real-time data analysis and competitive programming for fast range maximum queries.

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