Sliding Window Maximum Using Deque in DSA Rust - Build from Scratch

Sliding Window Maximum Using Deque

📖 Scenario: You are analyzing temperature readings collected every hour. You want to find the highest temperature in every 3-hour window to understand peak heat periods.

🎯 Goal: Build a Rust program that uses a deque to find the maximum temperature in each sliding window of size 3 from a list of hourly temperatures.

📋 What You'll Learn

Create a vector called temperatures with exact values: [73, 74, 75, 71, 69, 72, 76, 73]

Create a variable called window_size and set it to 3

Use a VecDeque to implement the sliding window maximum logic

Print the resulting vector of maximums for each window

💡 Why This Matters

🌍 Real World

Sliding window maximum is useful in real-time data analysis like temperature monitoring, stock price tracking, or network traffic analysis to quickly find peak values in recent data.

💼 Career

Understanding sliding window techniques and using data structures like deque is important for software engineers working on performance-critical applications, streaming data processing, and algorithm optimization.

1

Create the temperature data vector

Create a vector called temperatures with these exact values: [73, 74, 75, 71, 69, 72, 76, 73]

DSA Rust

# Create the temperatures vector with given values
# Your code here

Hint

Use let temperatures = vec![73, 74, 75, 71, 69, 72, 76, 73]; to create the vector.

2

Set the sliding window size

Create a variable called window_size and set it to 3

DSA Rust

fn main() {
    let temperatures = vec![73, 74, 75, 71, 69, 72, 76, 73];
    // Set the window size to 3
    // Your code here
}

Hint

Use let window_size = 3; to set the window size.

3

Implement sliding window maximum using VecDeque

Use a VecDeque called deque and a vector called max_values to find the maximum temperature in each sliding window of size window_size over temperatures. Use a for loop with variable i to iterate over indices of temperatures. Push indices into deque while maintaining decreasing order of values. Remove indices outside the current window. Append the maximum value for each full window to max_values.

DSA Rust

use std::collections::VecDeque;

fn main() {
    let temperatures = vec![73, 74, 75, 71, 69, 72, 76, 73];
    let window_size = 3;

    // Implement sliding window maximum using VecDeque
    // Your code here
}

Hint

Use VecDeque to store indices. Remove smaller values from back. Remove indices out of window from front. Add max values to max_values.

4

Print the sliding window maximum results

Print the vector max_values which contains the maximum temperatures for each sliding window.

DSA Rust

use std::collections::VecDeque;

fn main() {
    let temperatures = vec![73, 74, 75, 71, 69, 72, 76, 73];
    let window_size = 3;

    let mut deque: VecDeque = VecDeque::new();
    let mut max_values: Vec = Vec::new();

    for i in 0..temperatures.len() {
        while let Some(&back) = deque.back() {
            if temperatures[back] = window_size {
            if let Some(&front) = deque.front() {
                max_values.push(temperatures[front]);
            }
        }
    }

    // Print the max_values vector
    println!("{:?}", max_values);
}

Hint

Use println!("{:?}", max_values); to print the vector.

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