128 - Longest Consecutive Sequence

2020/05/02

leetcode

Problem

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

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Solution

Solution 1: Hash Map

For each value, we maintain the left bound and right bound of range and also update the bounds for left value and right value.

class Solution:
    def longestConsecutive(self, nums):
        h = dict()
        ans = 0

        for num in nums:
            if num not in h:
                if num - 1 in h and num + 1 in h:
                    h[h[num + 1][1]][0] = h[num - 1][0]
                    h[h[num - 1][0]][1] = h[num + 1][1]
                    h[num] = [h[num - 1][0], h[num + 1][1]]
                elif num - 1 in h:
                    h[h[num - 1][0]][1] += 1
                    h[num] = h[h[num - 1][0]]
                elif num + 1 in h:
                    h[h[num + 1][1]][0] -= 1
                    h[num] = h[h[num + 1][1]]
                else:
                    h[num] = [num, num]
                ans = max(ans, h[num][1] - h[num][0] + 1)

        return ans

Time: O(n)

Space: O(n)

Solution 2: Keep Counting!

Notice the if x - t not in nums.

class Solution:
    def longestConsecutive(self, nums):
        ans = 0
        nums = set(nums)
        for x in nums:
            if x - 1 not in nums:
                y = x + 1
                while y in nums:
                    y += 1
                ans = max(ans, y - x)
        return ans

Time: O(n)

Space: O(n)