LeetCode 128: Longest Consecutive Sequence

Problem Description

Difficulty: Medium

Given an array of integers nums, return the length of the longest consecutive sequence of elements.

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element.

Write an algorithm that runs in \(O(n)\) time.

Examples:

Input: nums = [2,20,4,10,3,4,5]
Output: 4
Explanation: The longest consecutive sequence is [2, 3, 4, 5].

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

Constraints:

0 <= nums.length <= 1000 on NeetCode or <= 10^5 on LeetCode
-10^9 <= nums[i] <= 10^9

Initial Solution

from typing import List

class InitialSolution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0

        nums_set = set(nums)  # set() is O(n) time
        longest_seq = 0

        for num in nums_set:
            if num - 1 not in nums_set:  # fails LeetCode without this
                current_num = num  # unnecessary new variable
                current_seq = 1

                while current_num + 1 in nums_set:
                    current_num += 1
                    current_seq += 1

                longest_seq = max(longest_seq, current_seq)

        return longest_seq

Test function

def test_longest_consecutive(solution_class):
    """Simple test function. Not extensive."""
    nums_empty = []
    nums0 = [0]
    nums1 = [2, 20, 4, 10, 3, 4, 5]
    nums2 = [0, 3, 2, 5, 4, 6, 1, 1]
    nums3 = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]

    nums_list = [nums_empty, nums0, nums1, nums2, nums3]
    expected = [0, 1, 4, 7, 9]

    solution = solution_class()
    results = [solution.longestConsecutive(nums) for nums in nums_list]

    if results == expected:
        print("Tests passed")
    else:
        print("Tests failed")
        print("Expected:", expected)
        print("Got:", results)

test_longest_consecutive(InitialSolution)

Tests passed

Intial Results

This seemed hard for a medium-level problem. I struggled to create something that didn’t involve sorting, as most sorting algorithms are \(n⋅log(n)\) or \(n^2\) time complexity. Radix and count sort are notable exceptions. My solution must be a pretty decent one as it beats 68% of submissions for run time, although it only beats 18% for memory. As we see later in NeetCode’s solution, mine has a few extra variables adding to the memory usage.

I needed to add the check to see if the number was already part of a sequence (if num - 1 not in nums_set:) to get it to pass LeetCode. The constraints are looser on NeetCode, so the original attempt was fine there, although slow. On LeetCode, it failed without the check (timed out) when given a really long consecutive sequence of length 100000. The key piece is that little check, as without it the time complexity is \(O(n⋅m)\), where \(n\) is the number of elements in nums, and \(m\) is the maximum length of a consecutive sequence. In the worst case, this is \(O(n^2)\) if the maximum length is a single long sequence of length \(n\).

• Time complexity: \(O(n)\) comprising \(O(n)\) for the set operation and \(O(n)\) to iterate over the set and perform checks.
• Space complexity: \(O(n)\) predominantly due to storing the set.

NeetCode Solution

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

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

test_longest_consecutive(Solution)

Tests passed

Conclusion

NeetCode’s solution is cleaner but essentially the same approach. It simplifies the tracking of the current sequence length within the while loop, saving a small amount of memory (it beats around 63% of submissions on memory).