Use a set for O(1) lookups and only start counting at sequence starts.
Insert all numbers into a set. For each number x, if x-1 isn’t in the set, treat x as the start and count upward until the chain ends.
Each number is visited in a counting loop at most once across all starts, giving linear time.
Use a set for O(1) lookups and only start counting at sequence starts.
Insert all numbers into a set. For each number x, if x-1 isn’t in the set, treat x as the start and count upward until the chain ends.
Each number is visited in a counting loop at most once across all starts, giving linear time.