Easy O(n) python code using map


  • 0
    X

    Put all number in a hashmap with value 0. The value means how many numbers are consecutive if search downwards. Then iterate through the array and do search from each element to update the hashmap. The idea is kind of like memoization.

    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def longestConsecutive(self, nums):
            dict = {}
            for i in nums: dict[i] = 0
            ans = 0
            for i in nums: 
                j = i - 1
                while j in dict and dict[j] == 0: j -= 1
                if j in dict:
                    tmp = j - dict[j]
                else:
                    tmp = j
                for j in xrange(j+1, i+1): dict[j] = j - tmp
                if dict[i] > ans: ans = dict[i]
            return ans

Log in to reply
 

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