128. Longest Consecutive Sequence

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        seen = set(nums)
        res = 0
        for n in seen:
            if n-1 not in seen:
                seq = n
                ln = 0
                while seq in seen:
                    seq += 1
                    ln += 1
                res = max(res,ln)
        return res        

Intuition:

Imagine placing the numbers of list on a number line. First we need to find the starting number of the sequence then count number of consecutive numbers and update the result. A sequence starts with number n if n-1 not in the set.

Approach

1. First creates a set of the input list called seen, which is used to keep track of which numbers have been visited. It also initializes a variable res to 0, which will be used to store the length of the longest consecutive sequence encountered so far.
2. Then iterates over each number n in seen, and checks if n-1 is not in seen. If this is true, then it means that n is the start of a new consecutive sequence. The method then enters a while loop that increments a variable seq by 1 and a variable ln by 1, as long as seq is in seen. This loop continues until seq is no longer in seen, meaning the end of the consecutive sequence has been reached.
3. After exiting the while loop, the method updates the res variable to be the maximum of res and ln, which ensures that res contains the length of the longest consecutive sequence seen so far. Finally, the method returns res as the output.

Time Complexity: O(n) as we visit each number only once

Space Complexity: O(n)