Algorithms to Compute the Longest Consecutive Sequence

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

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [100, 4, 200, 1, 3, 2]
Output
4
Explanation
The longest sequence of consecutive elements is [1, 2, 3, 4]. so we return its length: 4.

Example 2
Input
nums = [100, 4, 200, 1, 3, 2, 101, 105, 103, 102, 104]
Output
6
Explanation
The longest sequence of consecutive elements is [100, 101, 102, 103, 104, 105]. so we return its length: 6.

Bruteforce Algorithm to Compute the Longest Consecutive Sequence

We can first remember all numbers in a set. Then going through each number, we can try to build the longest consecutive sequence by checking if its plus-one is also in the set. Lookup time is O(1) because of a hash set however as the entire list may be the longest sequence, and for each number, it will take O(N) to follow the sequence, thus the complexity is O(N^2) quadratic.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def longestConsecutiveSequence(self, nums):
        if len(nums) == 0:
            return 0
        d = set(nums)
        ans = 1
        for i in nums:
            cur = 1
            while i + 1 in d:
                i += 1
                cur += 1
                ans = max(ans, cur)
        return ans

class Solution:
    def longestConsecutiveSequence(self, nums):
        if len(nums) == 0:
            return 0
        d = set(nums)
        ans = 1
        for i in nums:
            cur = 1
            while i + 1 in d:
                i += 1
                cur += 1
                ans = max(ans, cur)
        return ans

Better Bruteforce Algorithm to Compute the Longest Consecutive Sequence by using a Hash Table

We can use an additional hash map to remember (memoization) the longest consecutive sequence starting with this particular number, in this case we don’t need to repeatedly searching for intermediate answers. This reduce the complexity to O(N):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def longestConsecutiveSequence(self, nums):
        if len(nums) == 0:
            return 0
        d = set(nums)
        ans = 1
        nb = defaultdict(int)
        for i in nums:
            cur = 1            
            if i in nb:
                cur = nb[i]
            else:
                while i + 1 in d:
                    nb[i] = cur # memoization
                    i += 1
                    cur += 1            
            ans = max(ans, cur)
        return ans

class Solution:
    def longestConsecutiveSequence(self, nums):
        if len(nums) == 0:
            return 0
        d = set(nums)
        ans = 1
        nb = defaultdict(int)
        for i in nums:
            cur = 1            
            if i in nb:
                cur = nb[i]
            else:
                while i + 1 in d:
                    nb[i] = cur # memoization
                    i += 1
                    cur += 1            
            ans = max(ans, cur)
        return ans

Dynamic Programming Algorithm to Compute the Longest Consecutive Sequence

We can compute the longest sequence using . However, we need to sort the numebrs which will take O(NLogN) time.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def longestConsecutiveSequence(self, nums):
        if len(nums) == 0:
            return 0
        d = set(nums)
        dp = defaultdict(int)
        nums.sort()        
        for i in nums:
            dp[i] = max(dp[i], 1)
            if i - 1 in d:
                dp[i] = max(dp[i], dp[i - 1] + 1)
        return max(dp.values())

class Solution:
    def longestConsecutiveSequence(self, nums):
        if len(nums) == 0:
            return 0
        d = set(nums)
        dp = defaultdict(int)
        nums.sort()        
        for i in nums:
            dp[i] = max(dp[i], 1)
            if i - 1 in d:
                dp[i] = max(dp[i], dp[i - 1] + 1)
        return max(dp.values())

The above Dynamic Programming Algorithm to Compute the Longest Consecutive Sequence takes O(NLogN) time and O(N) space.

–EOF (The Ultimate Computing & Technology Blog) —