LESSON 315 OF 414 · SLIDING WINDOW

Longest Subarray Without Repeating Integers in Rust: O(n) Sliding Window

Given an input array of integers, find the length of the longest subarray without repeating integers.

Example

Input: nums = [2, 5, 6, 2, 3, 1, 5, 6]
Output: 5
Explanation: [5, 6, 2, 3, 1] or [6, 2, 3, 1, 5] are both valid and of maximum length 5

Note:

For this lesson, your algorithm should run in O(n) time and use O(n) extra space

STEP 1 OF 9

Guided

Ctrl + Enter to check

RUST · SLIDING WINDOW

Longest Subarray Without Reapeating in Rust, explained

Problem overview

The function longest_subarray_without_reapeating receives a vector of integers, nums, and returns the length of the longest subarray in which no value appears twice. A subarray is a run of neighbouring elements.

In the example, nums = [2, 5, 6, 2, 3, 1, 5, 6] gives 5. Both [5, 6, 2, 3, 1] and [6, 2, 3, 1, 5] have five different values, and no run of six elements is free of repeats. An empty vector gives 0.

Approach: two indices that only move right

The brute-force way is to start at every index, extend while the values stay distinct, and take the best. That is O(n^2) in the worst case, because every start can walk far to the right.

The lesson's version avoids the repeated walking. It keeps a HashSet holding the values of the current window, and two indices:

i, the start of the window, which the for loop advances one step at a time;
j, the next element to try to add, which stays where it stopped.

Suppose the window nums[i..j] has no repeats. When the start moves to i + 1, the window nums[i + 1..j] still has no repeats, because it is a part of a repeat-free window. So j doesn't need to go back. It continues from where it was, and only the one value that left, nums[i], has to be taken out of the set.

Each index is inserted into the set once, when j passes it, and removed at most once, when i passes it. Looking a value up in the set costs O(1) on average, so the whole scan is O(n).

Here is the example. For i = 0, j adds 2, 5 and 6, then stops at the second 2: the set holds 3 values. Then 2 leaves the set. For i = 1, the set is {5, 6}, so j adds 2, 3 and 1 and stops at the second 5. The set holds five values, which is the answer.

Step by step

Create the set unique_nums. It is declared mut because inserting and removing change it. It holds the values of the current window, so the check for a repeat is a lookup.
Create result as an i32, starting at 0. An empty vector never changes it.
Create j as a usize, before the loop over i. Declaring it outside is what keeps the scan linear, since j never restarts.
Loop over every start i, from 0 to the end of the vector.
Extend the window. A while loop runs as long as j is inside the vector and nums[j] isn't in the set. The two conditions are joined with &&, which stops at the first false one, so nums[j] is never read with j out of range. contains takes a reference, hence &nums[j].
Insert nums[j] and move j forward. Rust has no ++, so it is j += 1.
Record the length. When the loop stops, the window is nums[i..j], and the set holds exactly its values, so the set's len() is the window length. Keep the larger of that and result. len() is a usize, so it is cast with as i32.
Remove nums[i] from the set, because the next window starts one step later. j stays.
Return result as the final expression, with no semicolon.

The solution in Rust

use std::collections::HashSet;

impl Solution {
    fn longest_subarray_without_reapeating(nums: Vec<i32>) -> i32 {
        let mut unique_nums: HashSet<i32> = HashSet::new();
        let mut result: i32 = 0;
        let mut j: usize = 0;
        for i in 0..nums.len() {
            while j < nums.len() && !unique_nums.contains(&nums[j]) {
                unique_nums.insert(nums[j]);
                j += 1;
            }
            result = result.max(unique_nums.len() as i32);
            unique_nums.remove(&nums[i]);
        }
        result
    }
}

The Rust details worth a closer look:

HashSet comes from std::collections. It isn't in the prelude, so the use line is required.
References in contains and remove. Both take a reference to the value, so the code passes &nums[j] and &nums[i]. insert takes the value itself. For an i32 that is a copy, so nums[j] is still usable afterwards.
Return values of the set methods. insert returns a bool, true if the value was new, and remove returns true if the value was present. The code ignores both. That is allowed, because a bool isn't marked #[must_use].
Why remove always finds its value. At the end of iteration i, nums[i] is in the set. If the window was empty, the loop has just inserted it. If it wasn't, the window starts at i, and its first element is nums[i].
usize and i32. Indices and len() are usize, and the function returns i32, so the one place they meet needs as i32. The for range 0..nums.len() excludes the end, so i stops at the last valid index.

Complexity

Time: O(n). i takes n values. j only goes forward, so the inner while loop runs at most n times in total across the whole run. Inserts, lookups and removals are O(1) on average.

Space: O(n). The set holds at most one entry per element, in the case where all values are different.

Edge cases and common mistakes

Empty vector. The loop doesn't run and the result stays 0.
One value repeated. [4, 4, 4] returns 1. Each window holds a single 4, and it is removed before the next one starts.
All values different. [1, 2, 3] returns 3. The first window covers everything, and j reaches the end.
Window that must move in the middle. [1, 2, 1, 3, 4, 2] returns 4, from [2, 1, 3, 4]. The second 1 blocks the first window at length 2, and the second 2 blocks the next window at length 4.
Forgetting to remove nums[i]. The set would keep a value that is no longer in the window, and later values equal to it would be treated as repeats.
Resetting j inside the loop. The answer would stay correct only if the set were rebuilt each time, which brings back O(n^2).
Using j - i and len() interchangeably. They are equal here, but j - i is a usize and needs the same cast.

Testing

nums = [2, 5, 6, 2, 3, 1, 5, 6] gives 5.
nums = [1, 2, 1, 3, 4, 2] gives 4.
nums = [4, 4, 4] gives 1.
nums = [1, 2, 3] gives 3.
nums = [7] gives 1.
nums = [] gives 0.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free