Problem overview
The function longest_consecutive takes an unsorted vector of integers, nums, and returns the length of the longest run of values that follow each other by exactly 1, such as 1, 2, 3, 4. The run does not have to appear in order inside the vector, and duplicates count once.
For [100, 4, 200, 1, 3, 2] the values 1, 2, 3 and 4 form a run of length 4, while 100 and 200 stand alone, so the answer is 4. For [0, 2, 0, 1, 2, 3, 1] the answer is also 4: the run is 0, 1, 2, 3, and each value is counted once even though 0, 1 and 2 appear twice.
The statement asks for O(n) time and O(n) extra space, which rules out sorting (O(n log n)).
Approach: start counting only at the beginning of a run
The slow idea is to take every number and keep asking whether the next one is present. That is fast only if "is it present?" is cheap, so the first step is to put all the numbers in a HashSet, where a membership test takes constant time on average. As a bonus, the set removes duplicates, which is exactly what the problem wants.
Walking forward from every number would still be wasteful. In the run 1, 2, 3, 4 it would walk from 1, then again from 2, from 3 and from 4, and a long run would cost quadratic time. The fix is to walk only from the first number of a run. A number is the first of its run exactly when value - 1 is not in the set. Every other number is skipped immediately, because the walk that starts at the true beginning of its run will pass over it.
Each number is therefore visited at most twice: once by the outer loop, and at most once more by the walk of the run it belongs to. That gives O(n) overall.
On [100, 4, 200, 1, 3, 2] the set is {100, 4, 200, 1, 3, 2}. The value 100 has no 99, so a walk starts there and stops at once with length 1. The value 200 does the same. The value 4 is skipped because 3 is present, and so are 3 and 2. The value 1 has no 0, so the walk checks 2, 3 and 4 and stops at 5: length 4.
Step by step
- Keep the best length in
result, a mutablei32that starts at 0. That start value is also the right answer for an empty vector. - Build the set.
nums.into_iter().collect()consumes the vector and gathers its elements into aHashSet<i32>. The type annotation tellscollectwhich collection to build. - Loop over the set by reference, with the pattern
&valueso thatvalueis a plaini32. Borrowing keeps the set usable inside the loop. - Test for the start of a run with
!values.contains(&(value - 1)). Only then does a walk begin. - Start the length at 1, because the run already contains
value. - Walk forward. While
value + sequence_lengthis in the set, add 1 to the length. The loop stops at the first missing number. - Update the best length with
result.max(sequence_length). - Return
resultas the final expression, with no semicolon.
The solution in Rust
use std::collections::HashSet;
impl Solution {
fn longest_consecutive(nums: Vec<i32>) -> i32 {
let mut result = 0i32;
let values: HashSet<i32> = nums.into_iter().collect();
for &value in &values {
if !values.contains(&(value - 1)) {
let mut sequence_length = 1i32;
while values.contains(&(value + sequence_length)) {
sequence_length += 1;
}
result = result.max(sequence_length);
}
}
result
}
}
Rust details worth knowing:
collectfollows the annotation. The sameinto_iter().collect()would build aVecif the variable were annotated as one. HereHashSet<i32>makes it insert each element, dropping repeats.into_iter()moves the vector. After the call,numscan't be used any more, which is fine because the set now holds everything that matters.containstakes a reference. That is why the calls readcontains(&(value - 1)): the arithmetic is parenthesised, and the&borrows the result.for &value in &valuesiterates over&i32items. The&valuepattern copies each number out of its reference. AHashSetiterates in an unspecified order, which doesn't matter here because the answer is a maximum.- Integer overflow. The lessons build with optimizations, where
value - 1andvalue + sequence_lengthwrap silently at the ends of thei32range; a debug build would panic instead. For ordinary inputs this never comes up, but with[i32::MAX, i32::MIN]the walk fromi32::MAXwraps around toi32::MINand the function returns 2 instead of 1.
Complexity
Time: O(n) on average. Building the set inserts n numbers. The outer loop visits each distinct number once, and the inner while loop runs only from the start of a run, so across the whole function it advances over each number at most once. Hash lookups are constant time on average.
Space: O(n). The set holds up to n distinct numbers.
Edge cases and common mistakes
- Empty vector. The set is empty, the loop never runs and the function returns 0.
- Duplicates.
[7, 7, 7]returns 1. The set holds a single 7, so equal values never extend a run. - Negative numbers.
[-2, -1, 0, 1]returns 4. Nothing in the method cares about the sign. - Gaps.
[1, 2, 4, 5, 6, 8]returns 3, from the run 4, 5, 6. A gap of even one number ends a run. - Walking from every number. Dropping the
!values.contains(&(value - 1))check still gives correct answers but loses theO(n)bound, because runs get re-walked from each of their members. - Sorting instead of hashing. It works, but it costs
O(n log n)and does not meet the lesson's budget. - Counting duplicates twice. A sorted-array approach has to skip equal neighbours explicitly; the set does that automatically.
Testing
[100, 4, 200, 1, 3, 2]gives4.[0, 2, 0, 1, 2, 3, 1]gives4.[]gives0.[5]gives1.[1, 2, 4, 5, 6, 8]gives3.
