Python: A solution with some added flexibility


  • 0
    M

    It's late and I ended up parsing other solutions for insights on how to solve this (learning how to properly do this in the process but implementing this from scratch). My version has a bit more going on but for the sake of the original solution the extra output is presented as a class variable.

    Using max_set you can get the longest set. It's a bit more costly in terms of memory (though for this method you're already constrained by memory available) but it makes debugging it simpler.

    Note: If you have more than one longest sequence with the same length, the one you get out of this will be valid but not necessarily the same as other sequences of the same maximal length (such an ordering isn't prescribed in the problem statement, but of course neither is showing the inner workings...)

    A human-readable explanation of the solution by analogy:

    You are given a container with chips inside, each inscribed with a unique number. You select a chip at random and remove it.

    You then locate and remove the chip numbered one less than the original chip (if present), then the one less than that, and so on, repeating until you cannot find a lower numbered chip in that consecutive sequence.

    Likewise, you will remove the chip numbered one more than the original chip (if available), then the next, and so on, until you cannot find a higher numbered chip in that consecutive sequence.

    Count the chips. If it is more than the previous bunch, this becomes the current max sequence.

    At this point no chip still in the bag would directly continue any of the sequences you've already removed from it.

    Select another starting chip at random and repeat the process until the bag is empty.

    class Solution(object):
        max_set = set()
    
        def longestConsecutive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            s = set(nums)
            while s:
                n = s.pop()
                tset = set([n])
    
                s_neg = n-1
                while s_neg in s:
                    s.remove(s_neg)
                    tset.add(s_neg)
                    s_neg -= 1
    
                s_pos = n+1
                while s_pos in s:
                    s.remove(s_pos)
                    tset.add(s_pos)
                    s_pos += 1
    
                if len(self.max_set) < len(tset):
                    self.max_set = tset
            return len(self.max_set) 
    

Log in to reply
 

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