Longest Consecutive Sequence

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

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

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 needs a value to index map, parent links and sizes, where the hash set walk needs one set.

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.

Follow-up

Suppose values arrive one at a time and after each you must report the longest run so far. Can you keep the answer current 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. Sorting lines them up in O(n log n). A hash set 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: O(n) in total.

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, then x+2, until a value is missing, and keep the longest count. Every run has a smallest value in nums, and the loop walks the whole run from it.

Each search reads up to n values, and a long run is walked again from every member. For 10^4 values that form one shuffled run, the walks take about n²/2 = 5 × 10^7 steps, each scanning half the array on average: 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.

Walk the sorted values and keep the length of the current run. A value one more than the previous extends it. A repeat neither extends the run nor ends it, so skip it. Any other value starts a new run of length 1.

The sort costs O(n log n) and the walk O(n). Sorting in place needs no extra array; 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

With every value in a hash set, a membership check costs O(1) on average and repeats collapse into one 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 walk only from the first value of a run, which is exactly a value x whose x-1 is missing. In example 1 only 1 and 39 qualify, giving runs of 4 and 3.

Every value belongs to one run and is stepped over only by that run's walk, so all walks together take at most n steps. With one check per value, the total is O(n) time and O(n) memory for the set.

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

Treating a repeat as a gap or 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. One run of 10^4 values then costs 5 × 10^7 steps.
Looping over nums instead of the set. If the first value of a run of 2,500 appears 2,000 times, the run is walked 2,000 times.
Indexing an array by value. Values reach ±10^9, so it needs 2 × 10^9 entries.

Frequently asked questions3

What is the time complexity of Longest Consecutive Sequence?

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

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 needs a value to index map, parent links and sizes, where the hash set walk needs one set.

def longestConsecutive(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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 questions3

Similar problems