Longest Consecutive Sequence O(n) solution in python


  • 0
    T

    I used a dictionary to store the head index and length of a consecutive sequences.

    And every time we insert a number, I just check if the number has ancestor and successor. If yes, because the ancestor must be the end number of last consequence, so we can easily get the head index and update its length (plus one or plus the length of next consequence if it has successor). Vice versa, the successor must be the head of next consequence, from which we can know the length and the tail index of the next consequence, then we need to update the head of its tail number to point to the current head. So the general idea is that we only need to maintain the head and tail number. So the insertion is constant time complexity.

    By only one traversal, we can have all the consecutive sequences with its head and length. Then we just need to scan the dictionary once to find the max length. The time complexity is O(2n) = O(n) and the space complexity is O(n).

    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def longestConsecutive(self, nums):
            nums_dict = {}
            for i in nums:
                if i not in nums_dict:
                    nums_dict[i] = [i,1]
                    if i-1 in nums_dict:
                        nums_dict[i][0] = nums_dict[i-1][0]
                    if i+1 in nums_dict:
                        nums_dict[i][1] = nums_dict[i+1][1] + 1
                    if nums_dict[i][0] != i:
                        nums_dict[nums_dict[i][0]][1] += nums_dict[i][1]
                    nums_dict[i+nums_dict[i][1]-1][0] = nums_dict[i][0]
            max = 0
            for key in nums_dict:
                if nums_dict[key][1] > max:
                    max = nums_dict[key][1]
            return max

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.