Longest Consecutive Sequence

1. The obvious way

   Sort and scan: O(n log n). Or extend a run from every number by searching a list: O(n²).

2. The key insight

   Put all numbers in a set. A number whose predecessor is in the set is in the middle of a chain: skip it. A number without a predecessor is a chain head: walk forward while the next number exists. Every number is walked over at most once, so it is O(n).

3. The algorithm
   1. Put all numbers in a set.
   2. For each number: is its predecessor in the set? Then it is mid-chain, skip.
   3. Otherwise it is a head: count how far the chain goes forward (number+1, number+2, ...).
   4. Keep the longest chain length seen.

Watch it run

longest = 1

def longest_consecutive(nums):
    present = set(nums)
    longest = 0
    for number in present:
        if number - 1 in present:          # not the head of a chain
            continue
        length = 1
        while number + length in present:  # walk forward along the chain
            length += 1
        longest = max(longest, length)
    return longest

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.