Problem overview
The method longestConsecutive receives an unsorted array of integers and returns the length of the longest run of consecutive numbers, that is, values such as 1, 2, 3, 4 that each differ from the next by exactly 1. The numbers need not be neighbours in the array, and the order they appear in doesn't matter.
For [100, 4, 200, 1, 3, 2] the answer is 4, from the run 1, 2, 3, 4. In [0, 2, 0, 1, 2, 3, 1] the run 0, 1, 2, 3 also has length 4: repeated values count once.
The statement asks for O(n) time and O(n) extra space, which rules out sorting, since sorting takes O(n log n).
Approach: start counting only at the start of a run
Put every number in a hash set. That gives constant-time answers to "is this value present?" and removes duplicates. Then, for any number, you can ask whether the number just above it exists, and keep walking upward through the set.
Done naively, that walk is expensive: starting from every number would re-walk the same run many times, since the walk from 1 passes through 2, 3 and 4, and the walks from 2, 3 and 4 repeat it. The fix is to walk only from the first number of each run. A number is the first of its run exactly when value - 1 is not in the set. Each run is then walked once, so every number is visited a constant number of times in total, and the whole algorithm is O(n) even though it contains a loop inside a loop.
Step by step
- Start the best length at 0.
resultis avarset to 0, which is also the correct answer for an empty array. - Fill the set.
valuesis an emptySet<Int>, and a loop inserts every number ofnums. - Loop over the set with
for value in values. Looping over the set instead of the array skips duplicates. - Find run starts.
if !values.contains(value - 1)is true only for the first number of a run. Other numbers are skipped because their run is measured from its real start. - Begin counting with
var sequenceLength = 1, as the run already containsvalue. - Extend the run.
while values.contains(value + sequenceLength)checks the next number the run would need; each time it is present, add 1 tosequenceLength. - Keep the best. After the
whileloop, setresulttomax(result, sequenceLength). - Return
resultafter theforloop.
Tracing the example
For [100, 4, 200, 1, 3, 2] the set holds 100, 4, 200, 1, 3 and 2. Among these, 100, 200 and 1 are run starts, because 99, 199 and 0 are missing. From 100, 101 is missing, so that run has length 1. From 200 the length is also 1. From 1 the loop finds 2, 3 and 4 and stops at the missing 5, so the length is 4. The numbers 2, 3 and 4 are skipped, since 1, 2 and 3 are in the set. The result is 4.
The solution in Swift
class Solution {
func longestConsecutive(_ nums: [Int]) -> Int {
var result = 0
var values = Set<Int>()
for value in nums {
values.insert(value)
}
for value in values {
if !values.contains(value - 1) {
var sequenceLength = 1
while values.contains(value + sequenceLength) {
sequenceLength += 1
}
result = max(result, sequenceLength)
}
}
return result
}
}
Swift details worth a closer look:
- Iteration order doesn't matter. A
Setis visited in an unspecified order that can change between runs. The algorithm gives the same answer in any order, because it asks only about membership. - Reading while looping is fine. The loop only calls
containson the set. It never changesvaluesafter the first loop, so there is no conflict between iterating and reading. - Reusing a name.
valuenames the loop variable in bothforloops. That is legal, because each one exists only inside its own loop. - Integer arithmetic traps on overflow.
value - 1andvalue + sequenceLengthare computed on 64-bitInt. With a value ofInt.minor nearInt.max, that arithmetic would stop the program rather than wrap around. Ordinary inputs are far from these limits.
Complexity
Time: O(n). Building the set is O(n). In the second loop, the while loop runs only for run starts, and each number belongs to exactly one run, so the while loop's iterations add up to at most the number of distinct values. Every contains call is constant time on average.
Space: O(n). The set stores each distinct value once.
Edge cases and common mistakes
- Empty array. Returns 0. Starting
resultat 1 would wrongly return 1. - One element.
[5]returns 1. - Duplicates.
[0, 2, 0, 1, 2, 3, 1]returns 4, because the set holds each value once. - Negative numbers.
[-2, -1, 0]returns 3. Runs can cross zero. - Dropping the run-start test. The result is still correct, but a long run is re-walked from each of its members, which makes the worst case
O(n²). - Sorting and looking at neighbours. This works too, but the sort makes it
O(n log n)and duplicates need extra care.
Testing
[100, 4, 200, 1, 3, 2]gives 4.[0, 2, 0, 1, 2, 3, 1]gives 4.[]gives 0.[5]gives 1.[-2, -1, 0]gives 3.
