Python solution in HashMap with explanation

  • 3
    class Solution(object):
        def longestConsecutive(self, nums):
            :type nums: List[int]
            :rtype: int
            unions = {};
            maxlen = 0;
            for n in nums:
                if unions.has_key(n): # duplicate n, skip
                start = end = n;
                if unions.has_key(n+1): # update end if has bigger neighbouring section
                    end = unions[n+1][1];
                if unions.has_key(n-1): # update start if has smaller neighbouring section
                    start = unions[n-1][0];
                unions[start] = unions[end] = unions[n]=(start,end);
                maxlen = max(end-start+1, maxlen);
            return maxlen;

    Each section marks its start and end.
    Given n, get its neighbouring sections (n == section.max+1 or n == section.min-1) in Hashmap in O(1) and meanwhile update their start and end.
    Finally return the max length of sections;

Log in to reply

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