"""
O(n)

Hash the array. Iterate over the hashtable and start counting only from those numbers whose preceding number does not exist in hashtable and then keep checking and counting after that for building the sequence.

Although the time complexity appears to be quadratic due to the while loop nested within the for loop, closer inspection reveals it to be linear. Because the while loop is reached only when currentNum marks the beginning of a sequence (i.e. currentNum-1 is not present in nums), the while loop can only run for nnn iterations throughout the entire runtime of the algorithm. This means that despite looking like O(n⋅n) complexity, the nested loops actually run in O(n+n) = O(n)O(n+n)=O(n) time. All other computations occur in constant time, so the overall runtime is linear.
"""

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:

        if not len(nums):
            return 0

        hashmap = set(nums)
        longest_streak = float('-inf')

        for num in hashmap:
            if num - 1 not in hashmap:
                streak_starting_here = 1
                current_num = num
                while(current_num+1 in hashmap):
                    streak_starting_here+= 1
                    current_num += 1

                longest_streak = max(streak_starting_here, longest_streak)

        return longest_streak