Problem overview
The function longestConsecutive receives an unsorted IntArray called nums and returns the length of the longest run of consecutive integers that can be formed from its values, such as 1, 2, 3, 4. The run doesn't have to appear in order in the array, and a value that occurs several times counts once.
In the first example, [100, 4, 200, 1, 3, 2], the values 1, 2, 3, 4 form a run of length 4, and no run is longer, so the answer is 4. In the second, [0, 2, 0, 1, 2, 3, 1], the repeats are ignored: the distinct values 0, 1, 2, 3 give length 4.
The statement asks for O(n) time and O(n) extra space.
Approach: start counting only at the start of a run
The easy way to meet a time limit like O(n log n) is to sort the array and scan for neighbours that differ by one. The linear solution uses a hash set instead, which can answer "is x + 1 present?" in constant time.
A naive version would start from every value and count upward as long as the next number exists. That repeats work: in [1, 2, 3, 4], starting from 1 walks four numbers, starting from 2 walks three, and so on, which is quadratic for a long run. The fix is to start only from the first number of each run. A number value is the first of its run exactly when value - 1 is not in the set. For every other number, the run it belongs to will be counted from its real start.
With that rule, every number is walked over once: either it is a start, or it is part of the walk from one start. The loops together do a linear amount of work, even though one sits inside another.
In the first example, only 1, 100 and 200 have no predecessor in the set. From 1 the walk finds 2, 3, 4 and stops at 5, giving length 4. From 100 and from 200 the walk ends at once, giving length 1 each. The best is 4.
Step by step
- Start the answer at 0.
resultis avarand holds the longest run found so far. Zero is also the right answer for an empty array. - Build the set.
valuesis an emptyHashSet<Int>, and a loop overnumsadds every number. Duplicates collapse, and membership tests become constant time. - Loop over the set. Iterating over
valuesinstead ofnumsskips repeated values automatically. - Find run starts. The test
!values.contains(value - 1)is true only for the first number of a run. - Start measuring. Inside the
if,sequenceLengthis avarset to 1, because the run already holdsvalue. - Extend the run. A
whileloop checksvalues.contains(value + sequenceLength), the next number the run would need, and incrementssequenceLengthwhile it is present. It stops at the first missing number. - Keep the best.
result = maxOf(result, sequenceLength). - Return
resultafter the loop.
The solution in Kotlin
class Solution {
fun longestConsecutive(nums: IntArray): Int {
var result = 0
val values = HashSet<Int>()
for (value in nums) {
values.add(value)
}
for (value in values) {
if (!values.contains(value - 1)) {
var sequenceLength = 1
while (values.contains(value + sequenceLength)) {
sequenceLength++
}
result = maxOf(result, sequenceLength)
}
}
return result
}
}
Kotlin details:
- Loop variables such as
valueare read-only. That is why the code counts with a separatevar sequenceLengthinstead of changingvalue. !values.contains(value - 1)can also be written(value - 1) !in values. Both mean the same.- The two loops both use the name
value. The first one is finished before the second begins, so they don't clash. - Do not change
valueswhile looping over it. This solution only reads from the set in the second loop, which is safe; adding or removing there could throw aConcurrentModificationException. Intis 32 bits, sovalue - 1andvalue + sequenceLengthwrap around at the ends of the range. WithInt.MIN_VALUE,value - 1wraps toInt.MAX_VALUE, which can make a run look like it has a predecessor. For the two-element array holdingInt.MIN_VALUEandInt.MAX_VALUE, the reference solution returns 2 although the two numbers are not consecutive. It is the kind of limit a 32-bitIntbrings.
Complexity
Time is O(n). Building the set takes n constant-time additions. In the second loop, the while loop only runs from run starts, and each number is passed over by at most one such walk, so all walks together take at most n steps. Space is O(n) for the set.
Edge cases and common mistakes
- Empty array. The result stays 0.
- Duplicates.
[1, 1, 1]returns 1, since each value counts once. - Negative numbers.
[-1, 0, 1]returns 3; the run may cross zero. - Skipping the predecessor test. The answer is still correct, but the time becomes
O(n²)on a long run, which breaks the limit. - Looping over
numsin the second loop. It still works, but repeated values trigger repeated walks, so use the set. - Starting
sequenceLengthat 0. The run already containsvalue, so it starts at 1.
Testing
[100, 4, 200, 1, 3, 2]returns4.[0, 2, 0, 1, 2, 3, 1]returns4.[]returns0.