Sliding Window Maximum Using Deque in DSA C

Mental Model

Keep track of useful elements in a window using a double-ended queue to quickly find the maximum.

Analogy: Imagine a line of people waiting to enter a room, but only the tallest people stay in line because shorter ones behind them can't be the tallest in the group.

Array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size = 4
Deque stores indices of elements in decreasing order of values
Deque: front -> [index of max] -> ... -> back
Example:
Window: 2 1 3 4
Deque: [0 -> 2 -> 3] (values 2 -> 3 -> 4)

Dry Run Walkthrough

Input: array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56], window size k=4

Goal: Find maximum for each sliding window of size 4

Step 1: Process first 4 elements to initialize deque

Deque indices: [3] (values: 4)
Window: [2, 1, 3, 4]

Why: We keep only indices of elements that could be max; smaller ones removed

Step 2: Slide window by 1: remove indices outside window and add new element 6

Deque indices: [4] (values: 6)
Window: [1, 3, 4, 6]

Why: Remove index 0 (2) as it's out of window; remove smaller elements before 6

Step 3: Slide window by 1: add element 3, keep max at front

Deque indices: [4, 5] (values: 6, 3)
Window: [3, 4, 6, 3]

Why: 3 is smaller than 6, so it stays behind 6 in deque

Step 4: Slide window by 1: add element 8, remove smaller elements

Deque indices: [6] (value: 8)
Window: [4, 6, 3, 8]

Why: Remove 6 and 3 as 8 is bigger; 8 becomes new max

Step 5: Slide window by 1: add element 9, remove smaller elements

Deque indices: [7] (value: 9)
Window: [6, 3, 8, 9]

Why: Remove 8 as 9 is bigger; 9 is new max

Step 6: Slide window by 1: add element 10, remove smaller elements

Deque indices: [8] (value: 10)
Window: [3, 8, 9, 10]

Why: Remove 9 as 10 is bigger; 10 is new max

Step 7: Slide window by 1: add element 12, remove smaller elements

Deque indices: [9] (value: 12)
Window: [8, 9, 10, 12]

Why: Remove 10 as 12 is bigger; 12 is new max

Step 8: Slide window by 1: add element 56, remove smaller elements

Deque indices: [10] (value: 56)
Window: [9, 10, 12, 56]

Why: Remove 12 as 56 is bigger; 56 is new max

Result:

Maximums per window: [4, 6, 6, 8, 9, 10, 12, 56]

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Deque structure to store indices
typedef struct {
    int *data;
    int front;
    int rear;
    int size;
    int capacity;
} Deque;

Deque* createDeque(int capacity) {
    Deque *dq = (Deque*)malloc(sizeof(Deque));
    dq->data = (int*)malloc(sizeof(int)*capacity);
    dq->front = 0;
    dq->rear = -1;
    dq->size = 0;
    dq->capacity = capacity;
    return dq;
}

int isEmpty(Deque *dq) {
    return dq->size == 0;
}

void pushBack(Deque *dq, int val) {
    dq->rear = (dq->rear + 1) % dq->capacity;
    dq->data[dq->rear] = val;
    dq->size++;
}

void popBack(Deque *dq) {
    if (dq->size == 0) return;
    dq->rear = (dq->rear - 1 + dq->capacity) % dq->capacity;
    dq->size--;
}

void popFront(Deque *dq) {
    if (dq->size == 0) return;
    dq->front = (dq->front + 1) % dq->capacity;
    dq->size--;
}

int front(Deque *dq) {
    return dq->data[dq->front];
}

int back(Deque *dq) {
    return dq->data[dq->rear];
}

void slidingWindowMaximum(int *arr, int n, int k) {
    Deque *dq = createDeque(n);

    // Process first k elements
    for (int i = 0; i < k; i++) {
        // Remove smaller elements from back
        while (!isEmpty(dq) && arr[i] >= arr[back(dq)]) {
            popBack(dq); // remove smaller elements
        }
        pushBack(dq, i); // add current index
    }

    // Process rest of the elements
    for (int i = k; i < n; i++) {
        printf("%d ", arr[front(dq)]); // max of previous window

        // Remove indices out of this window
        while (!isEmpty(dq) && front(dq) <= i - k) {
            popFront(dq); // remove old indices
        }

        // Remove smaller elements
        while (!isEmpty(dq) && arr[i] >= arr[back(dq)]) {
            popBack(dq); // remove smaller elements
        }

        pushBack(dq, i); // add current index
    }

    // Print max of last window
    printf("%d\n", arr[front(dq)]);

    free(dq->data);
    free(dq);
}

int main() {
    int arr[] = {2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 4;
    slidingWindowMaximum(arr, n, k);
    return 0;
}

while (!isEmpty(dq) && arr[i] >= arr[back(dq)]) { popBack(dq); }

Remove smaller elements from back to keep deque decreasing

pushBack(dq, i);

Add current index to deque

printf("%d ", arr[front(dq)]);

Print max element of current window at front of deque

while (!isEmpty(dq) && front(dq) <= i - k) { popFront(dq); }

Remove indices out of current window from front

Output

4 6 6 8 9 10 12 56

Complexity Analysis

Time: O(n) because each element is added and removed at most once from the deque

Space: O(k) because deque stores at most k indices for the current window

vs Alternative: Naive approach is O(n*k) by scanning each window fully; deque approach is much faster with O(n)

Edge Cases

Window size k is 1

Each element is its own max; deque stores one index at a time

DSA C

while (!isEmpty(dq) && arr[i] >= arr[back(dq)]) { popBack(dq); }

Window size k equals array length

Only one max is printed for entire array

DSA C

printf("%d\n", arr[front(dq)]);

Array with all equal elements

Deque keeps indices in order; max is same for all windows

DSA C

while (!isEmpty(dq) && arr[i] >= arr[back(dq)]) { popBack(dq); }

When to Use This Pattern

When asked to find maximum or minimum in every sliding window efficiently, use the deque pattern to maintain candidates and achieve O(n) time.

Common Mistakes

Mistake: Not removing indices that are out of the current window from the front of the deque
Fix: Add a check to pop from front when front index is outside the window: while (!isEmpty(dq) && front(dq) <= i - k) popFront(dq);

Mistake: Not removing smaller elements from the back before adding new element
Fix: Before pushing new index, pop all smaller elements from back to keep deque decreasing

Summary

Find maximum in each sliding window using a deque to track useful elements.

Use when you need fast max/min queries over sliding windows in arrays.

Keep deque elements in decreasing order and remove outdated indices to maintain max at front.

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