Intuition

Most of the cases, if the question asks for O(1), there’s probably a set or hashmap involced.

This question uses the set to check if the next number is in the set (making a sequence)

Approach

The key is that the set provides a near O(1) access, making the solution O(n)

Complexity

  • Time complexity:

  • Space complexity:

Code

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        longest = 0

        num_set = set(nums)

        for num in num_set:
            if num-1 not in num_set:
                current = num
                curr_streak = 1
                while current + 1 in num_set:
                    current += 1
                    curr_streak += 1
                longest = max(curr_streak, longest) 
        return longest