Sliding Window Maximum Using Deque in DSA Rust - 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 for the array [1, 3, -1, -3, 5, 3, 6, 7] with window size 3 using a deque?

DSA Rust

fn sliding_window_maximum(nums: Vec<i32>, k: usize) -> Vec<i32> {
    use std::collections::VecDeque;
    let mut deq: VecDeque<usize> = VecDeque::new();
    let mut result = Vec::new();
    for i in 0..nums.len() {
        while let Some(&back) = deq.back() {
            if nums[back] < nums[i] {
                deq.pop_back();
            } else {
                break;
            }
        }
        deq.push_back(i);
        if let Some(&front) = deq.front() {
            if front + k <= i {
                deq.pop_front();
            }
        }
        if i + 1 >= k {
            result.push(nums[*deq.front().unwrap()]);
        }
    }
    result
}

fn main() {
    let nums = vec![1, 3, -1, -3, 5, 3, 6, 7];
    let k = 3;
    let output = sliding_window_maximum(nums, k);
    println!("{:?}", output);
}

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

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

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

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

💡 Hint

Remember the deque stores indices of elements in decreasing order of their values within the current window.

The sliding window maximum for each window of size 3 is computed by maintaining a deque of indices of elements in decreasing order. The maximum for each window is the element at the front of the deque. For the given array and window size, the maximums are [3, 3, 5, 5, 6, 7].

🧠 Conceptual

intermediate

Understanding Deque Behavior in Sliding Window Maximum

In the sliding window maximum algorithm using a deque, what is the main reason for removing elements from the back of the deque when a new element arrives?

A To ensure the deque only contains elements from the current window.

B To keep the deque elements sorted in increasing order of their values.

C To remove elements that are smaller than the new element since they cannot be maximum in the current or future windows.

D To maintain the deque size equal to the window size.

💡 Hint

Think about why smaller elements behind a bigger element are useless for maximum queries.

Elements smaller than the new element are removed from the back because they cannot be the maximum in the current or any future window that includes the new element. This keeps the deque in decreasing order of values, allowing quick access to the maximum.

🔧 Debug

advanced

Identify the Bug in Sliding Window Maximum Implementation

Given the following Rust code snippet for sliding window maximum, what error or bug will it cause when run?

DSA Rust

fn sliding_window_maximum(nums: Vec<i32>, k: usize) -> Vec<i32> {
    use std::collections::VecDeque;
    let mut deq: VecDeque<usize> = VecDeque::new();
    let mut result = Vec::new();
    for i in 0..nums.len() {
        while let Some(&back) = deq.back() {
            if nums[back] <= nums[i] {
                deq.pop_back();
            } else {
                break;
            }
        }
        deq.push_back(i);
        if let Some(&front) = deq.front() {
            if front + k < i {
                deq.pop_front();
            }
        }
        if i + 1 >= k {
            result.push(nums[*deq.front().unwrap()]);
        }
    }
    result
}

A The window expiry condition is incorrect, causing outdated indices to remain in the deque.

B The comparison operator in the while loop should be '<' instead of '<=' causing infinite loop.

C The deque is not cleared after each window, causing memory overflow.

D The code will panic due to unwrap on an empty deque when pushing results.

💡 Hint

Check the condition that removes indices outside the current window.

The condition 'if front + k < i' should be 'if front + k <= i' to correctly remove indices that are out of the current window. Otherwise, outdated indices remain, causing incorrect maximum values.

❓ Predict Output

advanced

Output of Sliding Window Maximum with All Equal Elements

What is the output of the sliding window maximum for the array [2, 2, 2, 2, 2] with window size 2 using a deque?

DSA Rust

fn sliding_window_maximum(nums: Vec<i32>, k: usize) -> Vec<i32> {
    use std::collections::VecDeque;
    let mut deq: VecDeque<usize> = VecDeque::new();
    let mut result = Vec::new();
    for i in 0..nums.len() {
        while let Some(&back) = deq.back() {
            if nums[back] < nums[i] {
                deq.pop_back();
            } else {
                break;
            }
        }
        deq.push_back(i);
        if let Some(&front) = deq.front() {
            if front + k <= i {
                deq.pop_front();
            }
        }
        if i + 1 >= k {
            result.push(nums[*deq.front().unwrap()]);
        }
    }
    result
}

fn main() {
    let nums = vec![2, 2, 2, 2, 2];
    let k = 2;
    let output = sliding_window_maximum(nums, k);
    println!("{:?}", output);
}

A [0, 0, 0, 0]

B [2, 2, 2, 2]

C [2, 2, 2]

D [2, 2, 2, 2, 2]

💡 Hint

All elements are equal, so maximum in each window is the same as the element value.

For window size 2, the number of windows is len(nums) - k + 1 = 4. Each window contains two 2's, so maximum is always 2. The output is [2, 2, 2, 2].

🧠 Conceptual

expert

Time Complexity of Sliding Window Maximum Using Deque

What is the time complexity of the sliding window maximum algorithm using a deque for an input array of size n and window size k?

A O(n) because each element is pushed and popped at most once from the deque.

B O(n * k) because each window requires scanning k elements.

C O(n log k) because of sorting elements inside each window.

D O(k) because the deque size is limited to k.

💡 Hint

Consider how many times each element is added and removed from the deque.

Each element is added to the deque once and removed once, so total operations are proportional to n. Hence, the time complexity is O(n).

Practice

1. For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k=3, what is the maximum of the first window [1,3,-1]?

easy

A. 1

B. -1

C. 3

D. 5

Solution

1. Step 1: First window

   Window [1, 3, -1] contains elements at indices 0, 1, 2.

2. Step 2: Maximum

   max(1, 3, -1) = 3.

3. Step 3: Deque state

   After processing first window: deque = [1] (index of 3, since 3 is largest and -1 is removed because 3 > -1 and 3 came before -1).

4. Final Answer:

   3 -> Option C

5. Quick Check:

   max(1,3,-1)=3. [OK]

Hint: max(1,3,-1)=3. Deque front holds index 1 (value 3) after processing window. [OK]

Common Mistakes:

• Returning the last element -1
• Returning the first element 1
• Not recognizing 3 as the maximum

2. In the sliding window maximum problem, what does the deque store?

medium

A. The maximum values seen so far

B. Indices of elements in decreasing order of their values

C. All elements in the current window

D. The sum of the current window

Solution

1. Step 1: Deque content

   The deque stores INDICES (not values), arranged so that nums[deque.front()] is always the maximum of the current window.

2. Step 2: Decreasing order

   Elements are kept in decreasing order of their values - smaller elements behind a larger one are useless (they can never be the maximum while the larger element is in the window).

3. Final Answer:

   Indices of elements in decreasing value order. -> Option B

4. Quick Check:

   Deque = indices in decreasing value order. Front = current window max. [OK]

Hint: Deque stores indices, decreasing by value. Front index = current max. [OK]

Common Mistakes:

• Thinking deque stores values not indices
• Thinking all window elements are stored
• Confusing with a max-heap approach

3. What is the time complexity of sliding window maximum using a monotonic deque?

medium

A. O(n²)

B. O(n log n)

C. O(n)

D. O(n × k)

Solution

1. Step 1: Each element pushed once

   Each element is pushed to the deque exactly once.

2. Step 2: Each element popped at most once

   Each element is popped from either front or back at most once. Total push+pop operations: 2n = O(n).

3. Step 3: Overall

   n iterations × O(1) amortized per iteration = O(n).

4. Final Answer:

   O(n) - each element pushed and popped at most once. -> Option C

5. Quick Check:

   Each element: 1 push + at most 1 pop = O(n) total. [OK]

Hint: Monotonic deque: each element pushed once, popped once = O(n). Better than O(n×k) naive. [OK]

Common Mistakes:

• Saying O(n×k) by not accounting for amortized analysis
• Saying O(n log n) confusing with heap-based approach
• Not knowing each element is pushed/popped at most once total

4. When processing a new element i in sliding window maximum, when do we pop from the BACK of the deque?

hard

A. When deque.back() index is outside the window

B. When nums[deque.back()] <= nums[i] - smaller elements are useless

C. When the deque is full (size == k)

D. When nums[i] is negative

Solution

1. Step 1: Why pop from back

   If nums[deque.back()] <= nums[i], the back element can never be the window maximum while nums[i] is in the window. nums[i] is larger AND will leave the window later.

2. Step 2: Keep decreasing order

   Pop all elements from back where nums[back] <= nums[i], then push i. This maintains the monotonic decreasing invariant.

3. Final Answer:

   Pop back when nums[deque.back()] <= nums[i]. -> Option B

4. Quick Check:

   Back pop: current element >= back element → back is useless, remove it. [OK]

Hint: Pop back when nums[back] <= nums[current]. Larger current makes smaller back useless forever. [OK]

Common Mistakes:

• Confusing front pop (out-of-window check) with back pop (useless element removal)
• Popping only when strictly less than, missing equals case
• Thinking deque size triggers back pop

5. When processing a new element i in sliding window maximum, when do we pop from the FRONT of the deque?

hard

A. When nums[deque.front()] < nums[i]

B. When deque.front() <= i - k (front index is outside the current window)

C. When the deque has more than k elements

D. When nums[i] is the new maximum

Solution

1. Step 1: Window boundary

   The current window is [i-k+1, i]. The front of deque holds the maximum's index. If that index <= i-k, it's outside the window.

2. Step 2: Pop expired maximum

   Pop front when deque.front() <= i - k. The front is no longer in the current window - the next front becomes the new maximum.

3. Final Answer:

   Pop front when front index <= i - k (out of window). -> Option B

4. Quick Check:

   Front pop: index out of window (front <= i-k). Back pop: value useless (back <= current). [OK]

Hint: Front pop = expired (index out of window). Back pop = useless (value smaller than current). [OK]

Common Mistakes:

• Confusing front pop condition with back pop condition
• Using < i-k instead of <= i-k (off by one)
• Thinking front pop is based on value comparison