Python solution using union-find

  • 0

    Explanation, find root of current number j, if the nums = [1,3,2] and j =2 , in two directions, we should find the root is [1,3],

        def longestConsecutive(self, nums):
            :type nums: List[int]
            :rtype: int
            h = {}
            max_count = 0
            for j in nums:
                if j in h: continue
                floor = ceil = j # up, down
                if j-1 in h:
                    floor = h[j-1][1]
                while floor in h and h[floor][1] != floor:
                    floor = h[floor][1]
                if j+1 in h: # up
                    ceil = h[j+1][0]
                while ceil in h and h[ceil][0] != ceil:
                    ceil = h[ceil][0]
                if j-1 in h:
                    h[j-1][0] = ceil
                if j+1 in h:
                    h[j+1][1] = floor
                h[j] = [ ceil, floor ]
                max_count = max(max_count, h[j][0]-h[j][1]+1)
            return max_count

Log in to reply

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