Sliding Window Maximum Using Deque in DSA Typescript - Deep Dive

Overview - Sliding Window Maximum Using Deque

What is it?

Sliding Window Maximum Using Deque is a method to find the largest number in every small section (window) of a bigger list of numbers. The window moves one step at a time from the start to the end of the list. A deque (double-ended queue) helps keep track of useful numbers so we can quickly find the maximum in each window. This method is faster than checking every window separately.

Why it matters

Without this method, finding the maximum in each window would take a lot of time, especially for big lists, making programs slow. This technique makes it possible to handle large data efficiently, like monitoring temperature changes or stock prices in real-time. It helps computers work faster and saves energy by avoiding repeated work.

Where it fits

Before learning this, you should understand arrays (lists) and basic queues. After this, you can learn other sliding window problems like sums or minimums, and advanced data structures like segment trees or heaps for range queries.

Mental Model

Core Idea

Keep only the useful candidates for maximum in a window using a deque to quickly find the max as the window slides.

Think of it like...

Imagine you are watching runners in a race from a moving window of seats. You only keep track of the fastest runners currently visible, ignoring slower ones behind them, so you always know who is leading without checking everyone again.

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

Deque stores indices of elements in decreasing order of their values:

Start:
Window [2,1,3,4]
Deque: [3 (value 4), 2 (value 3), 0 (value 2)]
Max: 4

Slide window by 1:
Window [1,3,4,6]
Remove index 0 (out of window)
Remove smaller values than 6
Deque: [4 (value 6)]
Max: 6

... and so on.

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.

A sliding window is a small section of a list that moves step-by-step from the start to the end. For example, if the list is [1,2,3,4,5] and the window size is 3, the windows are [1,2,3], then [2,3,4], then [3,4,5]. Each time the window moves, we look at the new group of numbers inside it.

Result

You can visualize the window moving over the list and understand which elements are inside at each step.

Understanding the sliding window is key because it breaks a big problem into smaller, manageable parts that move along the data.

2

Foundation

Basics of Deque Data Structure

Concept: Learn what a deque is and how it allows adding/removing from both ends.

A deque (double-ended queue) is like a line where you can add or remove people from the front or the back. This flexibility helps us keep track of important elements efficiently. For example, you can remove slow runners from the back and add new fast runners at the front.

Result

You understand how to use a deque to keep track of elements in order.

Knowing deque operations is essential because it lets us maintain a list of candidates for maximum without scanning the whole window every time.

3

Intermediate

Maintaining Maximum Candidates in Deque

🤔Before reading on: do you think the deque should store values or indices? Commit to your answer.

Concept: Store indices in the deque to know which elements are inside the current window and maintain decreasing order of their values.

We store indices of elements in the deque, not the values themselves. When a new element comes, we remove all smaller elements from the back because they can't be maximum if a bigger element is after them. We also remove indices that are out of the current window from the front.

Result

The deque always has indices of elements in decreasing order of their values, and all are inside the current window.

Storing indices instead of values allows us to quickly check if elements are still inside the window and maintain the correct order.

4

Intermediate

Sliding the Window and Updating Deque

🤔Before reading on: do you think we remove elements from the front or back of the deque when sliding the window? Commit to your answer.

Concept: Remove elements from the front if they are out of the window, and from the back if they are smaller than the new element.

Each time the window moves forward, check if the front of the deque is outside the window and remove it. Then, remove all smaller elements from the back before adding the new element's index. The front of the deque is always the maximum for the current window.

Result

After each slide, the deque correctly represents the maximum candidates for the new window.

Knowing when and where to remove elements keeps the deque efficient and ensures the maximum is always at the front.

5

Intermediate

Implementing Sliding Window Maximum in TypeScript

Concept: Write a complete function using deque to find maximums for all windows.

function slidingWindowMaximum(nums: number[], k: number): number[] { const deque: number[] = []; const result: number[] = []; for (let i = 0; i < nums.length; i++) { // Remove indices out of window while (deque.length && deque[0] <= i - k) { deque.shift(); } // Remove smaller elements from back while (deque.length && nums[deque[deque.length - 1]] < nums[i]) { deque.pop(); } deque.push(i); // Start adding max to result when first window is complete if (i >= k - 1) { result.push(nums[deque[0]]); } } return result; }

Result

For input [2,1,3,4,6,3,8,9,10,12,56], window size 4, output is [4,6,6,8,9,10,12,56]

Implementing the algorithm solidifies understanding and shows how deque operations translate into code.

6

Advanced

Time Complexity and Efficiency Analysis

🤔Before reading on: do you think the algorithm runs in O(n) or O(n*k) time? Commit to your answer.

Concept: The algorithm runs in O(n) time because each element is added and removed at most once from the deque.

Even though there are nested loops, each element is pushed and popped from the deque only once. This means the total operations related to the deque are proportional to the number of elements, making the algorithm linear in time.

Result

The sliding window maximum can be found in O(n) time, much faster than the naive O(n*k) approach.

Understanding the linear time complexity explains why this method is efficient for large data.

7

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: do you think the deque approach works if window size is 1 or equals array length? Commit to your answer.

Concept: The deque method gracefully handles edge cases like window size 1 or full array window, and can be optimized for memory and speed.

If window size is 1, the maximum is each element itself, and the deque will hold only one element at a time. If window size equals array length, the maximum is the max of the whole array. Optimizations include using a circular buffer for the deque or avoiding unnecessary array copies.

Result

The algorithm is robust and efficient for all valid window sizes and can be tuned for performance.

Knowing edge cases and optimizations prepares you for real-world scenarios and improves code reliability.

Under the Hood

The deque stores indices 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 anymore. The front of the deque always holds the index of the maximum element for the current window. As the window slides, indices outside the window are removed from the front. This ensures constant time access to the maximum for each window.

Why designed this way?

This design avoids re-scanning the window for maximum each time, reducing time from O(n*k) to O(n). Alternatives like heaps add overhead for removals. The deque approach is simple, uses less memory, and exploits the order of elements to maintain candidates efficiently.

Sliding Window Maximum Mechanism:

+-----------------------------+
|          Array              |
|  [2, 1, 3, 4, 6, 3, 8, 9]  |
+-----------------------------+
           ↓
+-----------------------------+
|          Deque              |
| Indices of max candidates   |
| Maintains decreasing values |
+-----------------------------+
           ↓
+-----------------------------+
|  Window slides right by 1   |
| Remove out-of-window indices |
| Remove smaller elements back |
| Front is max index          |
+-----------------------------+

Myth Busters - 4 Common Misconceptions

Quick: Do you think the deque stores the actual values or their indices? Commit to one.

Common Belief: The deque stores the actual values of the elements to find the maximum.

Reality: The deque stores indices, not values, to track which elements are inside the current window and maintain order.

Why it matters: Storing values would make it impossible to know if an element is outside the window, leading to incorrect maximums.

Quick: Do you think the algorithm checks every element in the window for max each time? Commit yes or no.

Common Belief: The algorithm scans all elements in the window every time it moves to find the maximum.

Reality: The algorithm never scans the entire window; it uses the deque to keep track of candidates, making it efficient.

Why it matters: Believing this leads to misunderstanding the efficiency and might cause writing slower code.

Quick: Do you think the deque can grow larger than the window size? Commit yes or no.

Common Belief: The deque can have more elements than the window size because it stores all candidates.

Reality: The deque size never exceeds the window size because it only holds indices of elements inside the current window.

Why it matters: Assuming otherwise can cause confusion about memory usage and performance.

Quick: Do you think the algorithm works only for positive numbers? Commit yes or no.

Common Belief: The sliding window maximum using deque only works correctly if all numbers are positive.

Reality: It works for any numbers, positive, negative, or zero, because it compares values directly.

Why it matters: This misconception limits the algorithm's perceived usefulness and might cause unnecessary restrictions.

Expert Zone

1

The deque approach implicitly maintains a monotonic queue, a powerful pattern for many range query problems beyond maximums.

2

In practice, using a circular buffer for the deque can reduce memory allocations and improve cache performance.

3

When multiple maximums have the same value, the algorithm preserves the earliest index, ensuring stable maximum selection.

When NOT to use

Avoid this method if you need to find maximums over non-contiguous or dynamic windows. For such cases, segment trees or balanced binary search trees are better. Also, if you need to find other statistics like median, specialized data structures like heaps or order-statistics trees are preferred.

Production Patterns

Used in real-time analytics like monitoring sensor data, stock price tracking, and network traffic analysis where quick maximum queries over sliding windows are critical. Also common in competitive programming and interview problems to demonstrate efficient range queries.

Connections

Monotonic Queue

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

Understanding monotonic queues helps generalize this technique to other problems like minimums or sums with constraints.

Real-time Signal Processing

Sliding window maximum algorithms are used to smooth or analyze signals in real-time systems.

Knowing this connection shows how algorithms directly impact hardware and software that process live data streams.

Project Management - Task Prioritization

Maintaining a deque of maximum candidates is like keeping track of highest priority tasks in a moving time frame.

This cross-domain link reveals how data structures mirror decision-making processes in everyday life.

Common Pitfalls

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

Wrong approach:

while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
deque.pop();
}
// Missing removal of out-of-window indices

Correct approach:

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

Root cause:

Not understanding that indices outside the window must be removed to keep the deque valid.

#2 Storing values instead of indices in the deque.

Wrong approach:

deque.push(nums[i]); // pushing values
if (deque[0] <= i - k) deque.shift(); // incorrect because deque stores values

Correct approach:

deque.push(i); // pushing indices
if (deque[0] <= i - k) deque.shift(); // correctly removes out-of-window indices

Root cause:

Confusing the need to track element positions with just their values.

#3 Starting to record maximums before the first full window is formed.

Wrong approach:

if (i >= 0) {
result.push(nums[deque[0]]);
}
// This adds max before window size is reached

Correct approach:

if (i >= k - 1) {
result.push(nums[deque[0]]);
}
// Starts after first full window

Root cause:

Not accounting for the window size when collecting results.

Key Takeaways

Sliding Window Maximum Using Deque efficiently finds maximums in all windows by maintaining a deque of candidate indices.

The deque stores indices in decreasing order of their values and removes elements outside the current window.

This approach runs in linear time, making it much faster than checking each window separately.

Understanding deque operations and window boundaries is essential to implement this correctly.

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

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