dumb Python O(n) solution


  • 0
    F
    class Solution(object):
        def longestConsecutive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            rd = dict()
            max_len = 0 
            start,end,val,l,r = 0,0,0,0,0
            for num in nums: 
                if num not in rd:
                    l = num - 1 
                    r = num + 1 
                    if r in rd and l in rd:
                        start, end, val = rd[l][0],rd[r][1],rd[r][2] + rd[l][2] +1
                        rd[rd[l][0]] = (start,end,val)
                        rd[num] = (start,end,val)
                        rd[rd[r][1]] = (start,end,val)
                    elif r in rd:
                        start,end,val =num,rd[r][1], rd[r][2] + 1
                        rd[num] = (start,end,val)
                        rd[rd[r][1]] = (start,end,val)
                    elif l in rd:
                        start,end,val = rd[l][0],num,rd[l][2] + 1
                        rd[num] = (start,end,val)
                        rd[rd[l][0]] = (start,end,val)
                    else:
                        rd[num] = (num, num, 1)
     
                    if rd[num][2] > max_len:
                        max_len = rd[num][2]
            return max_len 
            
            
    

Log in to reply
 

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