Longest Consecutive Sequence — No Sorting, Same Order

DISTRIBUTED MINDS

Array, exactly as given → [100, 4, 200, 1, 3, 2] — this order never changes.

Every number was looked up at most twice —
once entering the set, once during a walk.
That's the whole O(n).

100✓idx 0

4✓idx 1

200✓idx 2

1✓idx 3

3✓idx 4

2✓idx 5

100−1 = 99?

4−1 = 3?

200−1 = 199?

1−1 = 0?

3−1 = 2?

2−1 = 1?

missing

found

missing

found

length = 4

length = 1

👑

same order in, same order out 📝

# O(n) — a set, and one question. No sorting, ever.
def longestConsecutive(nums):
    numSet = set(nums)   # order of nums doesn't matter
    best = 0
    for n in numSet:            # any order works
        if (n - 1) not in numSet:
            length = 1
            while (n + length) in numSet:
                length += 1
            best = max(best, length)
    return best