Problem Statement

Given an integer array nums, return the length of the longest consecutive sequence that can be formed.

A consecutive sequence means each number is exactly 1 greater than the previous number.

The numbers do not need to appear next to each other in the original array.

We need to solve this in O(n) time.

Example

Input: nums = [2, 20, 4, 10, 3, 4, 5]
Output: 4

The longest consecutive sequence is:

[2, 3, 4, 5]

So the answer is 4.

Intuition

A brute-force approach would be to sort the array and then count consecutive numbers. However, sorting takes O(n log n)time, and the problem asks for an O(n) solution.

To achieve this, we can use a set.

A set allows us to check whether a number exists in O(1) average time.

The main idea is:

Only start counting a sequence from a number if it is the beginning of a sequence.

A number is the beginning of a sequence if:

num - 1 does not exist in the set

For example, in [2, 3, 4, 5], only 2 is the start because 1 is not present.

Then we keep checking:

num + 1
num + 2
num + 3
...

until the sequence ends.

Algorithm

  1. Convert nums into a set to remove duplicates and allow fast lookup.
  2. Initialize longest = 0.
  3. Loop through each number in the set.
  4. If num - 1 is not in the set, then num is the start of a sequence.
  5. Count how long the sequence is.
  6. Update longest.
  7. Return longest.

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        longest = 0

        for num in num_set:
            if num - 1 not in num_set:
                length = 1

                while num + length in num_set:
                    length += 1

                longest = max(longest, length)

        return longest

Walkthrough

For:

nums = [2, 20, 4, 10, 3, 4, 5]

Convert it into a set:

{2, 3, 4, 5, 10, 20}

Now check each number.

For 2:

2 - 1 = 1

1 is not in the set, so 2 is the start of a sequence.

Now count:

2, 3, 4, 5

Length is 4.

For 3, 4, and 5, we do not start counting again because each has a previous number in the set.

So the longest sequence is:

[2, 3, 4, 5]

Answer:

4

Time Complexity

O(n)

Each number is visited at most a constant number of times.

Space Complexity

O(n)

We store the numbers in a set.

Final Thoughts

The key trick is to only begin counting when we find the start of a sequence. This avoids repeated work and allows us to solve the problem in linear time.