My AC Python code using dictionary


  • 0
    H

    The idea is to store each consecutive range (i, i+1...j-1, j) in a dict like {i:j, j:i} and try to create a new range when a new number comes.

    class Solution(object):
        def longestConsecutive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
       
            D = {}  # for a consecutive range [i, j], we get D[i]=j and D[j]=i
            max_len = 0
            for x in nums:
                if x in D:  continue
                else:
                    new_l, new_r = x, x # prepare for a new range [new_l, new_r]
                    if x-1 in D:
                        new_l = min(x-1, D[x-1], new_l)
                        new_r = max(x, D[x-1], new_r)
                        D.pop(x-1)    # pop x-1 so that no overlapped range exists
                    if x+1 in D:
                        new_l = min(x, D[x+1], new_l)
                        new_r = max(x+1, D[x+1], new_r)
                        D.pop(x+1)
                    D[new_l], D[new_r] = new_r, new_l
                    max_len = max(abs(new_r-new_l+1), max_len)
                    
            return max_len
    

Log in to reply
 

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