Longest Consecutive Sequence

The goal is to find the longest consecutive sequence of integers than can be selected in the list given in argument. This list is unsorted and the selection has no rule. The algorithm must have a temporal complexity of O(n).

The idea of the algorithm is to use a set:

1. Cast the list in set to take advantage of the access by value in O(n) (instead of O(n))
2. Iterate over every value in the set and check if the next integers are also in the set
3. Keep the sequence length and compare it to the best already obtained
4. Also, store the values from the set that were already check in a sequence starting from another value. We won't have to check the sequence starting from this value as it would be part of a longer sequence

def longestConsecutive(nums: List[int]) -> int:
    # Cast nums in set as we do not care about duplicate values and set average access time is O(1); set_seen keeps already seen numbers
    set_nums, set_seen = set(nums), set()

    max_count = 0
    for i in set_nums:
        # Do not check again if i has already been seen; that means that a sequence starting with a smaller i has been checked
        if i not in set_seen:
            j = 0
            while i + j in set_nums:
                # Add i+j in set_seen in order to not check the sequence starting at i+j (shorter sequence than current one)
                set_seen.add(i + j)
                j += 1
            max_count = max(max_count, j)

    return(max_count)