Longest Consecutive Sequence

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

• Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.
• A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.
• You must write an algorithm that runs in  time.

Solution

• We can make a set of the numbers to make lookup , and then we can start only at possible beginnings of sequences.
  • We can find beginnings of sequences by checking if is not in the set, assuming
• Then, we can do a while loop checking if , and add to the local length of the sequence
  • We can do a simple to get the true longest out of all of the sequences

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
	    # time complexity: O(n)
	    # space complexity: O(n)
    
        num_set = set(nums)
        longest = 0
 
        for n in nums:
            if (n - 1) not in num_set:
                length = 0
                while (n + length) in num_set:
                    length += 1
                
                longest = max(length, longest)
        
        return longest

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───