128. Longest Consecutive Sequence - Explanation

Problem Link

Description

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

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.

You must write an algorithm that runs in O(n) time.

Example 1:

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

Output: 4

Explanation: The longest consecutive sequence is [2, 3, 4, 5].

Example 2:

Input: nums = [0,3,2,5,4,6,1,1]

Output: 7

Constraints:

  • 0 <= nums.length <= 1000
  • -10^9 <= nums[i] <= 10^9


Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.


Hint 1

A brute force solution would be to consider every element from the array as the start of the sequence and count the length of the sequence formed with that starting element. This would be an O(n^2) solution. Can you think of a better way?


Hint 2

Is there any way to identify the start of a sequence? For example, in [1, 2, 3, 10, 11, 12], only 1 and 10 are the beginning of a sequence. Instead of trying to form a sequence for every number, we should only consider numbers like 1 and 10.


Hint 3

We can consider a number num as the start of a sequence if and only if num - 1 does not exist in the given array. We iterate through the array and only start building the sequence if it is the start of a sequence. This avoids repeated work. We can use a hash set for O(1) lookups by converting the array to a hash set.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Brute Force

Intuition

A consecutive sequence grows by checking whether the next number (num + 1, num + 2, …) exists in the set.
The brute-force approach simply starts from every number in the list and tries to extend a consecutive streak as far as possible.
For each number, we repeatedly check if the next number exists, increasing the streak length until the sequence breaks.
Even though this method works, it does unnecessary repeated work because many sequences get recomputed multiple times.

Algorithm

  1. Convert the input list to a set for O(1) lookups.
  2. Initialize res to store the maximum streak length.
  3. For each number num in the original list:
    • Start a new streak count at 0.
    • Set curr = num.
    • While curr exists in the set:
      • Increase the streak count.
      • Move to the next number (curr += 1).
    • Update res with the longest streak found so far.
  4. Return res after checking all numbers.
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        res = 0
        store = set(nums)

        for num in nums:
            streak, curr = 0, num
            while curr in store:
                streak += 1
                curr += 1
            res = max(res, streak)
        return res

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n)

2. Sorting

Intuition

If we sort the numbers first, then all consecutive values will appear next to each other.
This makes it easy to walk through the sorted list and count how long each consecutive sequence is.
We simply move forward while the current number matches the expected next value in the sequence.
Duplicates don’t affect the result—they are just skipped—while gaps reset the streak count.
This approach is simpler and more organized than the brute force method because sorting places all potential sequences in order.

Algorithm

  1. If the input list is empty, return 0.
  2. Sort the array in non-decreasing order.
  3. Initialize:
    • res to track the longest streak,
    • curr as the first number,
    • streak as 0,
    • index i = 0.
  4. While i is within bounds:
    • If nums[i] does not match curr, reset:
      • curr = nums[i]
      • streak = 0
    • Skip over all duplicates of curr by advancing i while nums[i] == curr.
    • Increase streak by 1 since we found the expected number.
    • Increase curr by 1 to expect the next number in the sequence.
    • Update res with the maximum streak found so far.
  5. Return res after scanning the entire list.
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        res = 0
        nums.sort()

        curr, streak = nums[0], 0
        i = 0
        while i < len(nums):
            if curr != nums[i]:
                curr = nums[i]
                streak = 0
            while i < len(nums) and nums[i] == curr:
                i += 1
            streak += 1
            curr += 1
            res = max(res, streak)
        return res

Time & Space Complexity

  • Time complexity: O(nlog⁡n)O(n \log n)
  • Space complexity: O(1)O(1) or O(n)O(n) depending on the sorting algorithm.

3. Hash Set

Intuition

To avoid repeatedly recounting the same sequences, we only want to start counting when we find the beginning of a consecutive sequence.
A number is the start of a sequence if num - 1 is not in the set.
This guarantees that each consecutive sequence is counted exactly once.

Once we identify such a starting number, we simply keep checking if num + 1, num + 2, … exist in the set and extend the streak as far as possible.
This makes the solution efficient and clean because each number contributes to the sequence only one time.

Algorithm

  1. Convert the list into a set numSet for O(1) lookups.
  2. Initialize longest to track the length of the longest consecutive sequence.
  3. For each number num in numSet:
    • Check if num - 1 is not in the set:
      • If true, num is the start of a sequence.
      • Initialize length = 1.
      • While num + length exists in the set, increase length.
    • Update longest with the maximum length found.
  4. Return longest after scanning all numbers.
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        longest = 0

        for num in numSet:
            if (num - 1) not in numSet:
                length = 1
                while (num + length) in numSet:
                    length += 1
                longest = max(length, longest)
        return longest

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

4. Hash Map

Intuition

When we place a new number into the map, it may connect two existing sequences or extend one of them.
Instead of scanning forward or backward, we only look at the lengths stored at the neighbors:

  • mp[num - 1] gives the length of the sequence ending right before num
  • mp[num + 1] gives the length of the sequence starting right after num

By adding these together and including the current number, we know the total length of the new merged sequence.
We then update the left boundary and right boundary of this sequence so the correct length can be retrieved later.
This keeps the whole operation very efficient and avoids repeated work.

Algorithm

  1. Create a hash map mp that stores sequence lengths at boundary positions.
  2. Initialize res = 0 to store the longest sequence found.
  3. For each number num in the input:
    • If num is already in mp, skip it.
    • Compute the new sequence length:
      • length = mp[num - 1] + mp[num + 1] + 1
    • Store this length at num.
    • Update the boundaries:
      • Left boundary: mp[num - mp[num - 1]] = length
      • Right boundary: mp[num + mp[num + 1]] = length
    • Update res to keep track of the longest sequence.
  4. Return res after processing all numbers.
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        mp = defaultdict(int)
        res = 0

        for num in nums:
            if not mp[num]:
                mp[num] = mp[num - 1] + mp[num + 1] + 1
                mp[num - mp[num - 1]] = mp[num]
                mp[num + mp[num + 1]] = mp[num]
                res = max(res, mp[num])
        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)