Simple O(n) with Explanation - Just walk each streak
First turn the input into a set of numbers. That takes O(n) and then we can ask in O(1) whether we have a certain number.\n\nThen go through the numbers. If the
First turn the input into a *set* of numbers. That takes O(n) and then we can ask in O(1) whether we have a certain number.\n\nThen go through the numbers. If the number x is the start of a streak (i.e., x-1 is not in the set), then test y = x+1, x+2, x+3, ... and stop at the first number y *not* in the set. The length of the streak is then simply y-x and we update our global best with that. Since we check each streak only once, this is overall O(n). This ran in 44 ms on the OJ, one of the fastest Python submissions.\n\n    def longestConsecutive(self, nums):\n        nums = set(nums)\n        best = 0\n        for x in nums:\n            if x - 1 not in nums:\n                y = x + 1\n                while y in nums:\n                    y += 1\n                best = max(best, y - x)\n        return best
[]