Start learning free

LESSON 402 OF 576 · SLIDING WINDOW

Sliding Window Maximum in Rust: O(n) with a VecDeque

Practice O(n) Read the full explanation

You are given an array of integers nums and an integer k. A window of size k starts at the left end of nums and slides to the right one position at a time, until it reaches the right end. At each position, the window covers k neighbouring values.

Return an array with the largest value of each window, from left to right.

 

Example 1:

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation:
Window position                Max
---------------                ---
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

Input: nums = [1], k = 1
Output: [1]
Explanation: There is one window, and it holds the only value.

Example 3:

Input: nums = [7, 2, 4], k = 2
Output: [7, 4]
Explanation: The windows are [7, 2] and [2, 4]. Once 7 has left the window, 4 is the largest value.

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

Note:

Your algorithm should run in O(n) time, where n is the length of nums, and use O(n) extra space. Finding each window's maximum from scratch takes O(n · k) time, too slow for the largest tests.

STEP 1 OF 10
    Ctrl + Enter to check

    RUST · SLIDING WINDOW

    Sliding Window Maximum in Rust, explained

    Problem overview

    The function max_sliding_window receives a vector nums and a window size k. A window of k neighbouring values starts at the left end of nums and slides right one position at a time. The function returns the largest value of each window, from left to right, so the result has nums.len() - k + 1 entries.

    For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the windows are [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6] and [3, 6, 7]. Their maxima are [3, 3, 5, 5, 6, 7]. For [7, 2, 4] and k = 2 the answer is [7, 4]: once the 7 has left the window, the 4 is the largest value.

    The lesson asks for O(n) time. Scanning each window for its maximum costs O(n · k), which is too slow when both are in the tens of thousands.

    Approach: a deque of candidates

    The key observation is that most values can never be the answer again. Suppose a value a sits to the left of a value b and a <= b. Any window that contains a and also reaches b has b in it. And a leaves the window before b does, because it is further left. So as soon as b arrives, a is useless.

    The code keeps a deque, candidates, of the indexes of the values that can still be a window's maximum. Three rules hold it together:

    • The values behind the indexes decrease from front to back. When a new value arrives, every value at the back that is less than or equal to it is removed first.
    • The new index is then pushed at the back.
    • The front index is dropped when it has slid out of the window.

    The values decrease from front to back, and every dropped value was no bigger than one that stayed, so the front is always the maximum of the current window. Each index enters the deque once and leaves it at most once, so the work adds up to O(n) however big k is.

    The deque holds indexes, not values. The index tells you both the value (nums[index]) and whether the entry is still inside the window. Here is the deque for nums = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3 after each step:

    i=0 value=1 deque indexes=[0] values=[1]
i=1 value=3 deque indexes=[1] values=[3]
i=2 value=-1 deque indexes=[1, 2] values=[3, -1]
i=3 value=-3 deque indexes=[1, 2, 3] values=[3, -1, -3]
i=4 value=5 deque indexes=[4] values=[5]
i=5 value=3 deque indexes=[4, 5] values=[5, 3]
i=6 value=6 deque indexes=[6] values=[6]
i=7 value=7 deque indexes=[7] values=[7]

    At i = 4 the 5 removes all of 3, -1 and -3 from the back, because each is smaller. From i = 2 on the window is full, and the front's value is the maximum: 3, 3, 5, 5, 6, 7.

    Step by step

    1. Make k a usize. It arrives as an i32 but is compared with indexes. A new let k = k as usize; hides the old one for the rest of the function.
    2. Create the deque: a mutable VecDeque<usize> named candidates from VecDeque::new(). It adds and removes at both ends in constant time.
    3. Create result with Vec::new(). Rust infers its element type from what is pushed later.
    4. Loop over every index i in 0..nums.len(). Each turn i is the window's right end.
    5. Drop the front if it left the window. The window is the k values ending at i, so an index of i - k or less is outside it. The code tests front + k <= i instead of front <= i - k, because a usize can't hold a negative i - k while i < k.
    6. Drop weaker values from the back with a while loop, as long as the deque is not empty and nums[back] <= nums[i].
    7. Remove the back inside that loop with pop_back().
    8. Add i at the back with push_back(i). It is smaller than everything left in the deque, so the order stays decreasing.
    9. Record the maximum once the window is full. When i >= k - 1 the window holds k values, and the front's value goes into result.
    10. Return result without a semicolon.

    The solution in Rust

    use std::collections::VecDeque;

impl Solution {
    fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let mut candidates: VecDeque<usize> = VecDeque::new();
        let mut result = Vec::new();
        for i in 0..nums.len() {
            if !candidates.is_empty() && *candidates.front().unwrap() + k <= i {
                candidates.pop_front();
            }
            while !candidates.is_empty() && nums[*candidates.back().unwrap()] <= nums[i] {
                candidates.pop_back();
            }
            candidates.push_back(i);
            if i >= k - 1 {
                result.push(nums[*candidates.front().unwrap()]);
            }
        }
        result
    }
}

    The Rust details worth a closer look:

    • Shadowing. let k = k as usize; declares a new variable with the same name. The old i32 k can no longer be named, which avoids mixing the two types. The cast is safe because k is at least 1.
    • front() and back() return options. They give an Option<&usize>, None when the deque is empty. unwrap() takes out the reference, and * reads the number through it. The !candidates.is_empty() && before each call makes the unwrap safe, since && stops at the first false part.
    • pop_front() and pop_back() return the removed entry as an Option. The code doesn't need it, so it drops it.
    • Indexing with a dereferenced index. nums[*candidates.back().unwrap()] reads the value stored under the index at the back. The index has to be a usize to index a vector, which is why the deque holds usize.
    • k - 1 on a usize. It is safe because k is at least 1. With k = 0 it would underflow: a panic in a debug build and a wrap-around in an optimized one.
    • The use line. VecDeque lives in std::collections, and the lesson's code starts with the use line that brings it in.

    Complexity

    Time: O(n). The outer loop runs n times. Inside it, the if removes at most one entry, and the while loop removes entries that were each pushed exactly once. Over the whole run, at most n entries are pushed and at most n are popped, so all the pops together cost O(n).

    Space: O(n). The result holds n - k + 1 values, and the deque never holds more than k indexes.

    Edge cases and common mistakes

    • k = 1. Every window is a single value, so the result is nums itself. For [1, 2, 3, 4, 5] it is [1, 2, 3, 4, 5].
    • k equal to the length. There is one window. For [5, 4, 3, 2, 1] with k = 5 the result is [5].
    • Equal values. [4, 4, 4, 4] with k = 2 returns [4, 4, 4]. The <= in the while condition drops an equal value from the back, keeping the newer copy, which leaves the window later. Equal values are never both needed: the newer one stays in the window at least as long.
    • A decreasing input. Nothing is ever removed from the back, so the deque fills up to k entries and only the front check removes anything. [9, 8, 7, 6] with k = 2 returns [9, 8, 7].
    • Storing values instead of indexes. Then there is no way to tell when the front has left the window.
    • Writing i - k with unsigned numbers. While i < k it underflows: a panic in a debug build, a huge wrapped number in an optimized one. The lesson's form front + k <= i avoids subtraction.
    • Pushing results too early. Before index k - 1 the window is not yet a full window of the problem.

    Testing

    • nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 gives [3, 3, 5, 5, 6, 7].
    • nums = [1], k = 1 gives [1].
    • nums = [7, 2, 4], k = 2 gives [7, 4].
    • nums = [4, 4, 4, 4], k = 2 gives [4, 4, 4].
    • nums = [5, 4, 3, 2, 1], k = 5 gives [5].
    • nums = [1, 2, 3, 4, 5], k = 1 gives [1, 2, 3, 4, 5].
    • nums = [9, 8, 7, 6], k = 2 gives [9, 8, 7].
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free