Sliding Window Maximum Using Deque in DSA C - 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 continuous subarray of a fixed size within a bigger array. It uses a special list called a deque that allows adding and removing elements from both ends efficiently. This technique helps quickly find maximum values as the window moves through the array without checking all elements each time. It is useful for problems where you need to analyze data in chunks or windows.

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 data. This would make programs inefficient and slow, especially in real-time systems like video processing or stock price analysis. Using a deque speeds up the process, saving time and computing power, making applications faster and more responsive.

Where it fits

Before learning this, you should understand arrays, loops, and basic data structures like queues. After this, you can explore more complex sliding window problems, dynamic programming, or advanced data structures like segment trees and heaps.

Mental Model

Core Idea

Keep only useful elements in a special list so the front always shows the maximum for the current window.

Think of it like...

Imagine you are watching a parade and want to remember only the tallest people in each group passing by. You keep track of only those taller than anyone behind them, so you always know the tallest person without checking everyone again.

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

Deque stores indexes of elements:

i=0: [0] (2)
i=1: [0, 1] (2, 1)
i=2: [2] (3) - 0 and 1 removed (smaller than 3)
i=3: [3] (4) - 2 removed (smaller than 4)
Max for window 0-3: 4

i=4: [4] (6) - 3 removed (smaller than 6)
Max for window 1-4: 6

i=5: [4, 5] (6, 3)
Max for window 2-5: 6

i=6: [6] (8) - 4 and 5 removed (smaller than 8)
i=7: [7] (9) - 6 removed
i=8: [8] (10) - 7 removed
i=9: [9] (12) - 8 removed
i=10: [10] (56) - 9 removed

Max values: 4, 6, 6, 8, 9, 10, 12, 56

Build-Up - 6 Steps

1

Foundation

Understanding the Sliding Window Concept

Concept: Introduce the idea of a sliding window over an array and what it means to find maximums in each window.

A sliding window is a fixed-size group of elements that moves step-by-step over an array. For example, if the window size is 3 and the array is [1, 3, 2, 5, 4], the windows are [1,3,2], then [3,2,5], then [2,5,4]. Finding the maximum means picking the largest number in each window.

Result

You understand how windows move and what maximum means in this context.

Knowing how windows move helps you see why checking all elements every time is slow and why a better method is needed.

2

Foundation

Basics of Deque Data Structure

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

A deque (double-ended queue) lets you add or remove items from the front or back quickly. Unlike a normal queue or stack, it supports both ends. This makes it perfect for keeping track of candidates for maximum values as the window slides.

Result

You can use a deque to store elements or their indexes and update it efficiently.

Understanding deque operations is key to maintaining the maximum in constant time as the window moves.

3

Intermediate

Maintaining Maximum with Deque

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

Concept: Use the deque to store indexes of elements in a way that the front always points to the maximum in the current window.

We store indexes, not values, to know if elements are out of the current window. When a new element comes, remove all smaller elements from the back because they can't be maximum if a bigger element is after them. Then add the new element's index at the back. Remove front if it is out of the window range.

Result

Deque always has indexes of elements in decreasing order of their values, front is max.

Knowing to store indexes and remove smaller elements keeps the deque clean and efficient.

4

Intermediate

Sliding the Window and Extracting Maximums

🤔Before reading on: do you think the maximum is taken before or after sliding the window? Commit to your answer.

Concept: Slide the window one step at a time, update the deque, and record the maximum from the front of the deque.

Start by filling the deque for the first window. Then for each new element, slide the window by one: remove indexes out of range from front, remove smaller elements from back, add new index. The front of the deque is the max for the current window.

Result

You get a list of maximums for all windows in linear time.

Extracting max from the front after each slide avoids re-checking all elements.

5

Advanced

Implementing Sliding Window Maximum in C

🤔Before reading on: do you think the deque can be implemented using arrays or linked lists more efficiently in C? Commit to your answer.

Concept: Write a complete C program using arrays to implement the deque and solve the sliding window maximum problem.

Use an array to store deque indexes with two pointers: front and rear. Initialize them properly. For each element, update the deque as explained. Print maximums after processing each window. Handle edge cases like window size larger than array or empty array.

Result

A working C program that prints maximums for each sliding window.

Implementing deque with arrays in C requires careful pointer management but is efficient and practical.

6

Expert

Optimizations and Edge Case Handling

🤔Before reading on: do you think the algorithm still works if all elements are equal? Commit to your answer.

Concept: Explore how the algorithm behaves with duplicates, very large windows, or empty inputs and how to optimize memory and speed.

Duplicates are handled naturally because smaller or equal elements are removed from back. For very large windows equal to array size, the max is just the max of the whole array. For empty arrays or zero window size, handle gracefully by returning no output. Optimize by avoiding unnecessary memory allocations and using static arrays if size known.

Result

Robust and efficient sliding window maximum implementation ready for production.

Handling edge cases and optimizing memory ensures the algorithm is reliable and fast in all scenarios.

Under the Hood

The deque stores indexes of array elements in decreasing order of their values. When a new element arrives, all smaller elements at the back are removed because they can't be maximum anymore. The front 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 O(n).

Why designed this way?

This design avoids re-scanning the entire window for maximum each time it moves, which would be O(k) per window and O(nk) total. Using a deque to keep candidates in order leverages the fact that smaller elements behind a bigger one are useless for future windows. Alternatives like heaps add complexity and overhead. The deque approach is simple, fast, and uses minimal extra memory.

Input Array: [a0, a1, a2, ..., an-1]

Sliding Window Size: k

Process:

 ┌─────────────┐
 │   Window    │
 │ a[i]..a[i+k-1] │
 └─────────────┘
       ↓
 ┌─────────────────────────────┐
 │ Deque stores indexes in order│
 │ of decreasing values         │
 │                             │
 │ Front -> max index           │
 │ Back -> candidates           │
 └─────────────────────────────┘
       ↓
 Remove indexes out of window range from front
 Remove smaller elements from back
 Add new element index at back

Repeat for i = 0 to n-k

Myth Busters - 3 Common Misconceptions

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

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

Reality: The deque stores indexes of elements, not the values themselves, to track which elements are inside the current window.

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

Quick: Do you think all elements smaller than the current one should be kept in the deque? Commit to yes or no.

Common Belief: All elements smaller than the current element should be kept in the deque for future windows.

Reality: Smaller elements at the back are removed because they cannot be maximum if a bigger element comes after them.

Why it matters: Keeping smaller elements wastes memory and slows down the algorithm, losing the O(n) efficiency.

Quick: Does the algorithm still work correctly if all elements are equal? Commit to yes or no.

Common Belief: If all elements are equal, the deque method fails or behaves differently.

Reality: The algorithm works correctly with duplicates because equal elements are handled by removing smaller or equal elements from the back, preserving correctness.

Why it matters: Misunderstanding this can cause unnecessary code complexity or wrong assumptions about input data.

Expert Zone

1

The deque maintains a strict decreasing order of values by removing smaller or equal elements from the back, which is crucial for correctness and efficiency.

2

Storing indexes instead of values allows constant-time checks for whether elements are still inside the current window, avoiding extra data structures.

3

The algorithm guarantees each element is pushed and popped at most once, ensuring linear time complexity even for large inputs.

When NOT to use

This approach is not suitable when the window size changes dynamically or when you need other statistics like median or sum. For those, data structures like balanced trees, heaps, or segment trees are better choices.

Production Patterns

Used in real-time data streams for monitoring maximum values, in financial software for moving maximum prices, and in image processing for local maximum filters. Often combined with multi-threading or hardware acceleration for high-speed data.

Connections

Monotonic Stack

Similar pattern of maintaining elements in sorted order to solve range queries efficiently.

Understanding sliding window maximum helps grasp monotonic stacks used in histogram problems and next greater element queries.

Queue Data Structure

Deque is a double-ended queue, extending the basic queue concept with more flexible operations.

Knowing queues helps understand how deques work and why they are efficient for sliding window problems.

Real-Time Signal Processing

Sliding window maximum is used to detect peaks in signals over time windows.

Recognizing this connection shows how algorithms solve practical problems in engineering and science.

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_front_index < current_window_start) deque_pop_front(); // but forget to check window start

Correct approach:

while (!deque_empty && deque_front_index < current_window_start) deque_pop_front();

Root cause:

Not properly managing window boundaries causes outdated elements to remain, leading to wrong maximums.

#2 Storing values instead of indexes in the deque.

Wrong approach:

deque_push_back(array[i]); // storing values directly

Correct approach:

deque_push_back(i); // storing indexes to track window range

Root cause:

Confusing values with positions prevents checking if elements are still inside the sliding window.

#3 Not removing smaller elements from the back before adding a new element.

Wrong approach:

deque_push_back(i); // without removing smaller elements

Correct approach:

while (!deque_empty && array[deque_back] <= array[i]) deque_pop_back(); deque_push_back(i);

Root cause:

Failing to maintain decreasing order causes incorrect maximums and reduces efficiency.

Key Takeaways

Sliding Window Maximum Using Deque finds maximums in each window efficiently by storing indexes in a special list that keeps values in decreasing order.

The deque stores indexes, not values, to track which elements are inside the current window and remove outdated ones.

Removing smaller elements from the back before adding a new element keeps the deque clean and ensures the front is always the maximum.

Each element is added and removed at most once, making the algorithm run in linear time, which is much faster than naive methods.

Understanding this method prepares you for more complex sliding window problems and efficient real-time data processing.

Practice

1. What is the main purpose of using a deque in the Sliding Window Maximum problem?

easy

A. To store the sum of elements in each window

B. To sort the array elements before processing

C. To reverse the array for easier traversal

D. To store indices of elements in a way that helps find the maximum in O(1) time per window

Solution

1. Step 1: Understand the role of deque

   A deque stores indices of elements in a way that the front always has the index of the maximum element for the current window.

2. Step 2: Why deque helps in O(1) max retrieval

   Because the deque maintains elements in decreasing order, the maximum is always at the front, allowing quick access without scanning the window.

3. Final Answer:

   To store indices of elements in a way that helps find the maximum in O(1) time per window -> Option D

4. Quick Check:

   Deque stores max indices for O(1) max retrieval [OK]

Hint: Deque keeps max at front for quick max retrieval [OK]

Common Mistakes:

• Thinking deque stores actual values instead of indices
• Using deque to sort elements
• Using deque to store sums

2. Which of the following is the correct way to declare a deque in C for storing integer indices?

easy

A. struct deque dq; // assuming a deque struct is defined

B. deque<int> dq;

C. int dq[];

D. deque dq = new deque();

Solution

1. Step 1: Understand C data structure declaration

   C does not have built-in deque type; we use structs or arrays to implement it.

2. Step 2: Identify correct syntax

   struct deque dq; // assuming a deque struct is defined shows a struct declaration which is the correct way in C if a deque struct is defined.

3. Final Answer:

   struct deque dq; // assuming a deque struct is defined -> Option A

4. Quick Check:

   C uses structs for custom data types [OK]

Hint: Use struct for deque in C, no built-in deque type [OK]

Common Mistakes:

• Using C++ syntax like deque<int>
• Trying to declare deque like an array without size
• Using Java or other language syntax

3. What is the output of the sliding window maximum for array [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56] with window size 4?

medium

A. [3, 4, 6, 6, 8, 9, 10, 12, 56]

B. [2, 3, 4, 6, 8, 9, 10, 12]

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

D. [6, 6, 8, 9, 10, 12, 56]

Solution

1. Step 1: Slide window and find max for each window of size 4

   Windows and max values:
   Window 1: [2,1,3,4] max=4
   Window 2: [1,3,4,6] max=6
   Window 3: [3,4,6,3] max=6
   Window 4: [4,6,3,8] max=8
   Window 5: [6,3,8,9] max=9
   Window 6: [3,8,9,10] max=10
   Window 7: [8,9,10,12] max=12
   Window 8: [9,10,12,56] max=56

2. Step 2: Collect all max values in order

   The max values are [4, 6, 6, 8, 9, 10, 12, 56]

3. Final Answer:

   [4, 6, 6, 8, 9, 10, 12, 56] -> Option C

4. Quick Check:

   Max per window = [4,6,6,8,9,10,12,56] [OK]

Hint: Slide window, track max with deque front [OK]

Common Mistakes:

• Including partial windows smaller than size 4
• Off-by-one errors in window indexing
• Confusing max values with sums

4. Given this snippet for sliding window maximum, what is the bug?

for (int i = 0; i < n; i++) {
  while (!dq.empty() && arr[dq.back()] <= arr[i])
    dq.pop_back();
  dq.push_back(i);
  if (dq.front() <= i - k)
    dq.pop_front();
  if (i >= k - 1)
    printf("%d ", arr[dq.front()]);
}

medium

A. The condition to pop front should be < instead of <=

B. No bug, code is correct

C. The condition to pop front should be checked before pushing current index

D. The order of popping from back and pushing is wrong

Solution

1. Step 1: Analyze deque maintenance logic

   The code pops smaller elements from back before pushing current index, ensuring decreasing order.

2. Step 2: Check window boundary condition

   The code pops front if the front index is out of current window (<= i-k), which is correct.

3. Step 3: Confirm output printing

   Printing starts after first full window (i >= k-1), printing max at front index.

4. Final Answer:

   No bug, code is correct -> Option B

5. Quick Check:

   Deque logic and conditions are correct [OK]

Hint: Check deque front removal after pushing current index [OK]

Common Mistakes:

• Removing front before pushing current index
• Using wrong comparison operators in conditions
• Printing output before full window

5. How would you modify the sliding window maximum algorithm using deque to find the sliding window minimum instead?

hard

A. Change the comparison from arr[dq.back()] <= arr[i] to arr[dq.back()] >= arr[i] when popping from back

B. Reverse the array before applying the same algorithm

C. Use a stack instead of a deque

D. Change the window size to half

Solution

1. Step 1: Understand max vs min logic in deque

   For max, we pop from back while elements are smaller or equal. For min, we pop while elements are greater or equal.

2. Step 2: Modify comparison operator

   Change condition from arr[dq.back()] <= arr[i] to arr[dq.back()] >= arr[i] to maintain increasing order for min.

3. Final Answer:

   Change the comparison from arr[dq.back()] <= arr[i] to arr[dq.back()] >= arr[i] when popping from back -> Option A

4. Quick Check:

   Reverse comparison for min sliding window [OK]

Hint: Flip comparison sign to find min instead of max [OK]

Common Mistakes:

• Reversing array instead of changing comparison
• Using stack which doesn't maintain order
• Changing window size unnecessarily