8-liner in Python, simple BFS


  • 1
    O

    This is a standard BFS solution.

    class Solution(object):
        def longestConsecutive(self, nums):
            def bfs(start):
                q = [start] if start in toVisit else []
                for n in q:
                    toVisit.remove(n)
                    q += [x for x in [n-1, n+1] if x in toVisit]
                return len(q)
            toVisit = set(nums)
            return max(map(bfs, nums))
    

    Which is equivalent to:

    class Solution(object):
        def longestConsecutive(self, nums):
            def bfs(start):
                count, q = 0, []
                if start in d and not d[start]:
                    q.append(start)
                for n in q:
                    d[n] = True
                    q += [k for k in [n-1, n+1] if k in d and not d[k]]
                    count += 1
                return count
            d = {n:False for n in nums}
            return max(map(bfs, nums))
    

  • 0
    P

    This solution seems very elegant, but I have a hard time understanding it. Would you care to explain more?


  • 0
    C

    take my knee


Log in to reply
 

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