LeetCode 128 - Longest Consecutive Sequence - 2023.10.02 solution

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        """ If it was sorted, we could just track the longest sequence as
        we went.  But sorting is O(nlogn) time.  To get O(n) time we may need
        to use extra memory, like by using a dict. Also it's important to
        remember that we can go through the list multiple times and still have
        an O(n) solution.
        The question to ask yourself is: what would you want to know, when
        looking at each element, to know if it's the element you need to
        return?
        In our case, we'd want to know what the length of the sequence is of
        which this element is a part.  And then after iterating through the
        entire list and storing a variable to keep track of the longest
        sequence we've seen we'd have our answer.
        So the next question is: how could we determine the length of the sequence of
        each element as we came to that element? A: If we knew, for each element,
        whether there existed in the list the previous element and next
        element, we could traverse each sequence as we came to each element
        to determine its length.

        But we don't actually need to check *every* element as we come to
        it, but rather just
        one per sequence, and we'd get the answer (the length of the
        longest sequence). So which element of each sequence should we
        check?  The only ones we know will exist in every sequence are
        the first and last elements of the sequence because we can't just say
        'oh we'll use the second element' if we don't know if all the
        sequences are at least 2 long.
        So if we're only checking the length of a sequence for the first
        element, then we need to know, when we get to each element in the
        original list, whether it's the first of a sequence or not. And we
        can do that by using our dict to check if the number one less than it
        is in the list or not.

        So, what we need to know:
        - For each element, the index of an element with a value of 1 less
          than it, if such an element exists
        - For each element, the index of an element with a value 1 more than
          it, if it exists.
        - We could do this with one dict mapping from value to index.
        """
        num_set = set(nums)
        longest_length = 0
        for n in nums:
            if n - 1 in num_set:
                continue
            length = 0
            j = n
            while j in num_set:
                length += 1
                j += 1
            longest_length = max(length, longest_length)
        return longest_length