Sliding Window Maximum Using Deque in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sliding Window Maximum for a Simple Array

What is the output of the sliding window maximum algorithm using a deque for the array [1, 3, -1, -3, 5, 3, 6, 7] with window size 3?

DSA C

int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
int n = 8;
int k = 3;
// Sliding window maximum using deque logic applied here
// Output the maximums for each window

A [3, -1, -3, 5, 3, 6]

B [1, 3, -1, -3, 5, 3]

C [3, 3, 5, 5, 6, 7]

D [7, 6, 5, 3, -3, -1]

💡 Hint

Remember the deque keeps indexes of elements in decreasing order of their values.

The sliding window maximum for each window of size 3 is calculated by maintaining a deque that stores indexes of useful elements. The maximum for each window is the element at the front of the deque.

❓ Predict Output

intermediate

Sliding Window Maximum Output for All Negative Numbers

What is the output of the sliding window maximum algorithm using a deque for the array [-4, -2, -5, -1, -3] with window size 2?

DSA C

int arr[] = {-4, -2, -5, -1, -3};
int n = 5;
int k = 2;
// Sliding window maximum using deque logic applied here
// Output the maximums for each window

A [-4, -2, -5, -1]

B [-4, -5, -3, -1]

C [-1, -1, -3, -3]

D [-2, -2, -1, -1]

💡 Hint

Maximum in a window of negative numbers is the least negative (closest to zero).

The sliding window maximum for each window of size 2 is the maximum (least negative) element in that window. Using deque, we track indexes of elements in decreasing order.

🔧 Debug

advanced

Identify the Error in Sliding Window Maximum Implementation

Given the following code snippet for sliding window maximum using deque, what error will it cause when run?

DSA C

void slidingWindowMax(int arr[], int n, int k) {
    deque<int> dq;
    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()]);
    }
}

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;
    slidingWindowMax(arr, n, k);
    return 0;
}

A Correct output: 4 6 6 8 9 10 12 56

B Runtime error due to invalid deque access

C Compilation error due to missing header

D No output; infinite loop

💡 Hint

Check the condition for popping from front of deque carefully.

The code correctly maintains the deque and prints the maximum for each sliding window. The condition dq.front() <= i - k correctly removes indexes out of the current window.

🧠 Conceptual

advanced

Why Use Deque for Sliding Window Maximum?

Why is a deque the preferred data structure for implementing the sliding window maximum algorithm efficiently?

A Because deque automatically sorts elements, so maximum is always at front

B Because deque allows insertion and deletion from both ends in O(1) time, enabling efficient window updates

C Because deque stores elements in a tree structure for fast searching

D Because deque uses hashing to find maximum elements quickly

💡 Hint

Think about how the window slides and how elements are added or removed.

Deque supports adding and removing elements from both ends in constant time, which is essential for maintaining the sliding window and tracking maximums efficiently.

🚀 Application

expert

Find Maximum of Sliding Windows with Varying Sizes

Given an array and a list of window sizes, which approach correctly computes the maximum for each sliding window size using deque efficiently?

A Run the sliding window maximum algorithm separately for each window size using deque

B Use a single deque to process all window sizes simultaneously in one pass

C Sort the array once and pick maximums for all windows from sorted array

D Use a stack instead of deque to track maximums for all window sizes

💡 Hint

Consider how window size affects the sliding window maximum algorithm.

Each window size requires its own pass because the maximum depends on the window length. Using deque separately for each window size is efficient and correct.