Python O(n) solution using sets


  • 13
    Y
    class Solution:
        # @param num, a list of integer
        # @return an integer
        def longestConsecutive(self, num):
            num=set(num)
            maxLen=0
            while num:
                n=num.pop()
                i=n+1
                l1=0
                l2=0
                while i in num:
                    num.remove(i)
                    i+=1
                    l1+=1
                i=n-1
                while i in num:
                    num.remove(i)
                    i-=1
                    l2+=1
                maxLen=max(maxLen,l1+l2+1)
            return maxLen

  • 4

    Nice one. I wrote my own based on your idea, main difference being that I don't use extra length variables. I just find the first and last number in the streak and calculate the length as last-first+1:

    class Solution:
        def longestConsecutive(self, nums):
            nums = set(nums)
            maxlen = 0
            while nums:
                first = last = nums.pop()
                while first - 1 in nums:
                    first -= 1
                    nums.remove(first)
                while last + 1 in nums:
                    last += 1
                    nums.remove(last)
                maxlen = max(maxlen, last - first + 1)
            return maxlen

  • 1
    S

    Nice solution, but it is O( n^2), each i in num is O(n).

    https://wiki.python.org/moin/TimeComplexity


  • 0
    M

    You are amazing!


  • 1
    S

    num is converted into a set, so each "i in num" is now O(1)


Log in to reply
 

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