Python solution with detailed explanation


  • 0
    G

    Solution

    Longest Consecutive Sequence https://leetcode.com/problems/longest-consecutive-sequence/

    Algorithm 1

    • Add all the nums to a dictionary such that dictionary[num] = True.
    • For every element k, move up as far as you can go and then move down as far as you can go down. Invalidate the elements as you do this up and down walk. This makes sure that a number is processed just once for its longest streak and gives us a O(N) solution.
    class Solution(object):
        def longestConsecutive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            table, max_run = {k:True for k in nums}, 0
            for k in table:
                if table[k]:
                    # Move up
                    mid = k
                    while k in table and table[k]:
                        table[k], k = False, k-1
                    upper_run = mid-k
                    # Move down
                    k = mid + 1
                    while k in table and table[k]:
                        table[k], k = False, k+1
                    lower_run = k-mid-1
                    max_run = max(max_run, upper_run + lower_run)
            return max_run
    

    Algorithm 2

    class Solution(object):
        def longestConsecutive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            cache, max_run = set(nums), 0
            for x in nums:
                if x-1 not in cache:
                    y = x
                    while y in cache:
                        y += 1
                    max_run = max(max_run, y-x)
            return max_run
    

Log in to reply
 

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