Longest Consecutive Sequence

Q: What is the time complexity of Longest Consecutive Sequence?

The hash set solution runs in O(n) time on average and uses O(n) extra memory. Sorting and then counting runs takes O(n log n) time. Searching the array for each next value without a set takes up to O(n³) .

Q: Why is the hash set solution O(n) when it has a while loop inside a for loop?

The inner loop only runs from a value whose left neighbour x-1 is missing, which is the first value of its run. Each value is stepped over by the walk of its own run and by no other walk, so all inner loops together take at most n steps. The outer loop adds one check per value, for O(n) in total.

Q: Can union-find solve Longest Consecutive Sequence?

Yes. Make each distinct value a set, join x with x+1 whenever both are present, and return the size of the largest set. It runs in close to O(n) time, but it needs a value to index map, parent links and sizes, while the hash set walk does the same job with one set and two loops.

MediumHashing

+10

You get an array of integers nums in no particular order. A consecutive sequence is a group of values x, x+1, x+2 and so on, each of which appears somewhere in nums. Return the length of the longest consecutive sequence. A value that appears more than once counts once.

Function

longestConsecutive(nums: integer-array) → integer

numsinteger-array: the integers, in any order, repeats allowed
Returnsinteger: the length of the longest run of consecutive values present in nums

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Values may repeat. Positions in the array do not matter, only which values are present.

Examples

Input: nums = [40, 4, 39, 1, 3, 2, 41]
Output: 4
Explanation: 1, 2, 3 and 4 are all present, a run of 4, even though they are scattered through the array. The other run, 39 to 41, has only 3 values.

Input: nums = [7, 3, 7, 5, 6, 5]
Output: 3
Explanation: 5, 6 and 7 form a run of 3. The second 7 and the second 5 add nothing, and 3 cannot join because 4 is missing.

+17 hidden tests on Submit

Follow-up

Suppose the values arrive one at a time, and after each one you must report the longest run so far. Can you keep the answer up to date in O(1) average time per value?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The values of a run can sit anywhere in the array, so you cannot read runs off from left to right. Sorting lines them up in O(n log n). A hash set does better: it answers "is x+1 here?" in O(1), and if you count only from values whose x-1 is missing, each value is stepped over once, which makes the whole search O(n).

Count up from every value by searching the array

Correct, but does not finish on the largest tests

Intuition

Treat every value as the possible start of a run. From x, search the array for x+1; if it is there, search for x+2, and keep going until a value is missing. The number of values you reached is the run that starts at x, and the largest of these lengths is the answer.

It is correct because every run has a smallest value, that value is in nums, and the loop tries it as a start and walks the whole run. Repeats do no harm: they only try the same start twice.

It is slow on two counts. Each "is it here?" reads up to n values, and a long run is walked again from every one of its members. Take 10^4 values that form one shuffled run: the walks add up to about n²/2 = 5 × 10^7 steps, and each step scans on average half the array. That is around 2.5 × 10^11 comparisons.

Algorithm

Set best to 0.
For each value start in nums, set current to start and length to 1.
While a scan of nums finds current+1, add 1 to current and to length.
Store length in best if it is larger.
Return best.

def longestConsecutive(nums):
    best = 0
    for start in nums:
        current = start
        length = 1
        # "in" on a list reads it from the front until it finds the value.
        while current + 1 in nums:
            current += 1
            length += 1
        best = max(best, length)
    return best

Sort, then count runs

Intuition

Sorting puts the values of each run next to each other. [40, 4, 39, 1, 3, 2, 41] becomes [1, 2, 3, 4, 39, 40, 41], and the runs read off from left to right: 1 to 4, then a jump to 39.

Walk the sorted values and keep the length of the current run. A value one more than the previous extends it. A value equal to the previous is a repeat: skip it, because it neither extends the run nor ends it. Any other value is a gap, and a new run of length 1 starts there.

The sort costs O(n log n) and the walk O(n). Sorting in place needs no extra array but reorders the caller's input; languages that sort a copy use O(n) memory.

Algorithm

Sort nums in increasing order.
Set best and run to 1, since the array is never empty.
For each index i from 1, skip nums[i] if it equals nums[i-1].
If nums[i] is nums[i-1]+1, add 1 to run; otherwise set run to 1. Store run in best if it is larger.
Return best.

def longestConsecutive(nums):
    nums.sort()
    best = 1
    run = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            continue  # a repeat neither extends nor breaks the run
        if nums[i] == nums[i - 1] + 1:
            run += 1
        else:
            run = 1
        best = max(best, run)
    return best

Hash set, counting only from the start of each run

Intuition

Put every value in a hash set. Now "is x+1 present?" costs O(1) on average instead of a scan, and repeats collapse into a single entry.

Walking from every value would still repeat work: in the run 1, 2, 3, 4 you would take 3 steps from 1, 2 from 2 and 1 from 3. So start a walk only at the first value of a run. A value x is first exactly when x-1 is not in the set. In [40, 4, 39, 1, 3, 2, 41] only 1 and 39 qualify: from 1 you reach 4, a length of 4, and from 39 you reach 41, a length of 3.

Every value belongs to exactly one run, and only the walk from that run's first value steps over it, so all the walks together take at most n steps. Add one membership check per value and the build of the set, and the total is O(n) time with O(n) memory for the set.

Loop over the set, not over nums. If the first value of a run of 2,500 values appears 2,000 times in nums, looping over nums walks that run 2,000 times.

Algorithm

Put every value of nums in a hash set values, and set best to 0.
For each value x in the set, skip it if x-1 is in the set: it is not the first value of its run.
Otherwise set end to x and add 1 to it while end+1 is in the set.
Store end-x+1 in best if it is larger.
Return best.

def longestConsecutive(nums):
    values = set(nums)
    best = 0
    for value in values:
        # Only a value with no left neighbour starts a run.
        if value - 1 in values:
            continue
        end = value
        while end + 1 in values:
            end += 1
        best = max(best, end - value + 1)
    return best

Pitfalls and edge cases

Most wrong answers come from repeated values, and most slow answers from walking the same run more than once.

Treating a repeat as a gap or as a step after sorting. In [1, 2, 2, 3], resetting the run at the second 2 gives 2, and counting it as a step gives 4. The answer is 3.
Starting best at 0 in the sorted walk and updating it only inside the loop. An array of one value then returns 0 instead of 1.
Walking from every value of the set instead of only from run starts. The answer is right, but one run of 10^4 values costs 5 × 10^7 steps, the quadratic work the set was meant to remove.
Looping over nums instead of the set when values repeat. The run starting at a value that appears thousands of times is walked thousands of times.
Marking values in an array indexed by value. Values reach ±10^9, so the array would need 2 × 10^9 entries.

Frequently asked questions4

What is the time complexity of Longest Consecutive Sequence?

The hash set solution runs in O(n) time on average and uses O(n) extra memory. Sorting and then counting runs takes O(n log n) time. Searching the array for each next value without a set takes up to O(n³).

Why is the hash set solution O(n) when it has a while loop inside a for loop?

The inner loop only runs from a value whose left neighbour x-1 is missing, which is the first value of its run. Each value is stepped over by the walk of its own run and by no other walk, so all inner loops together take at most n steps. The outer loop adds one check per value, for O(n) in total.

Can you solve Longest Consecutive Sequence without extra memory?

Yes, if you may reorder the input: sort it in place and count runs in one pass, skipping repeats. That uses O(1) extra memory but O(n log n) time. The O(n) solution needs the hash set.

Can union-find solve Longest Consecutive Sequence?

Yes. Make each distinct value a set, join x with x+1 whenever both are present, and return the size of the largest set. It runs in close to O(n) time, but it needs a value to index map, parent links and sizes, while the hash set walk does the same job with one set and two loops.

Python

def longestConsecutive(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [40, 4, 39, 1, 3, 2, 41]

Expected

Longest Consecutive Sequence

Function

Constraints

Examples

Hints

Solution

Count up from every value by searching the array

Sort, then count runs

Hash set, counting only from the start of each run

Pitfalls and edge cases

Frequently asked questions4

Similar problems