Problem overview
The function longest_subarray_without_reapeating receives a vector of integers and returns the length of the longest subarray in which no value appears twice. A subarray is a run of neighbouring elements, so you can't skip over any.
For nums = [2, 5, 6, 2, 3, 1, 5, 6] the answer is 5. The run [5, 6, 2, 3, 1] has five different values. Extending it by the next element, 5, would repeat a value. [6, 2, 3, 1, 5] is another run of length 5.
This lesson asks for O(n²) time and O(n) extra space. A faster approach exists, and this lesson builds the simpler one that checks every starting point.
Approach: grow a subarray from every start until it breaks
Every subarray is fixed by its first index i and its last index j. The plan is to try every i, and for each one extend j to the right one element at a time, keeping the values seen so far in a hash set. As long as the next element isn't in the set, the subarray from i to j is valid and its length j - i + 1 is a candidate for the answer.
The first time the next element is already in the set, the loop stops. Any longer subarray from the same i would contain that repeat as well, so there is no reason to continue. The loop then moves to the next start.
Without the set, checking the new element would mean scanning the subarray, adding another factor of n. The set answers "have I seen this?" in O(1) on average, so the work is one inner loop of at most n steps for each of the n starts.
On [1, 2, 1]: from i = 0 the elements 1 and 2 are accepted (length 2), then the second 1 is in the set and the loop breaks. From i = 1, the elements 2 and 1 are accepted (length 2). From i = 2, the single 1 gives length 1. The answer is 2.
Step by step
- Keep the best length in
result, amut i32starting at 0. An empty vector never changes it, so the answer for it is 0. - Loop over the start index
iin0..nums.len(). The range excludes its end, soiis always a valid index. - Create a fresh set for each start.
unique_numsholds the values of the current subarray. It is created inside the loop so that each newibegins empty. - Loop over the end index
jini..nums.len(). Starting atimeans the first subarray checked has one element. - Check for a repeat. If
unique_numsalready containsnums[j], break out of the inner loop. - Record the length. The subarray from
itoj, both included, hasj - i + 1elements.resultbecomes the larger of itself and that length. Both indices areusize, so the length is converted withas i32. - Insert
nums[j]into the set after the check. Inserting first would make every element look like a repeat of itself. - Return
resultas the final expression.
The solution in Rust
use std::collections::HashSet;
impl Solution {
fn longest_subarray_without_reapeating(nums: Vec<i32>) -> i32 {
let mut result: i32 = 0;
for i in 0..nums.len() {
let mut unique_nums: HashSet<i32> = HashSet::new();
for j in i..nums.len() {
if unique_nums.contains(&nums[j]) {
break;
}
result = result.max((j - i + 1) as i32);
unique_nums.insert(nums[j]);
}
}
result
}
}
Rust details:
- Ranges.
0..nums.len()goes from 0 up to but not including the length. An empty vector gives an empty range, so the loop body never runs.i..nums.len()is an empty range wheniequals the length, which never happens inside the outer loop. - References.
containstakes a reference to the value, hence&nums[j].inserttakes the value itself, and ani32is copied, sonumskeeps its elements. - Casts.
j - i + 1is ausize. Sincej >= i, the subtraction can't go below zero. Theas i32cast is safe for any vector that fits in memory with fewer than 2^31 elements. maxis a method.result.max(x)returns the larger of twoi32values without using anif.breakleaves only the inner loop. The outer loop carries on with the nexti.
Complexity
Time: O(n²). There are n starting points, and each inner loop runs at most n steps, each with O(1) average set work. When all elements are different, no loop breaks early and the total is about n²/2 steps.
Space: O(n). The set holds at most the values of one subarray, up to n values, and a new set replaces it for every start.
Edge cases and common mistakes
- Empty vector. Returns 0.
- All elements equal.
[7, 7, 7]returns 1: every start accepts one element and then meets a repeat. - All elements different.
[1, 2, 3]returns 3, the whole vector. - Inserting before checking. Every value would then look like a duplicate, and the function would return 0.
- Reusing one set across starts. Values from an earlier start would leak into later subarrays and give wrong answers. Create the set inside the outer loop.
- Confusing subarrays with subsequences. In
[2, 5, 6, 2, 3, 1, 5, 6], choosing 2, 5, 6, 3, 1 skips an element, so it isn't a subarray.
Testing
[2, 5, 6, 2, 3, 1, 5, 6]gives 5.[]gives 0.[7, 7, 7]gives 1.[1, 2, 3]gives 3.
