Longest Consecutive Sequence

Given an unsorted array of integers, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Function signature

func LongestConsecutive(nums []int) int

Inputs / outputs

• nums: input slice of integers.
• Return: length of the longest consecutive sequence.

Example

nums = [100,4,200,1,3,2]
Output: 4

Sequence: 1,2,3,4

Constraints

• 0 <= len(nums) <= 100_000
• -1_000_000_000 <= nums[i] <= 1_000_000_000

Core idea (near-solution)

Use a hash set for O(1) membership. Only start counting from numbers that are sequence starts (i.e., x-1 is not in the set).

Invariant: each sequence is counted exactly once, from its smallest element.

Algorithm (step-by-step)

1. Insert all numbers into a set.
2. For each number x:
   • If x-1 is not in the set, start a new sequence.
   • Count how long it extends by checking x+1, x+2, ...
3. Track the maximum length.

Correctness sketch

• Invariant: each sequence is counted exactly once, from its smallest element.
• The map counts/associations are updated consistently per element.
• Lookups use this exact state, so decisions are based on full prior data.
• Therefore the result is correct for the entire input.

Trace (hand walkthrough)

Example input:
nums = [100,4,200,1,3,2]
Output: 4

Sequence: 1,2,3,4

Walk:
- set={100,4,200,1,3,2}; start at 1 (0 missing)
- extend 1->2->3->4 length=4
- other numbers are not starts -> best=4

Pitfalls to avoid

• Counting sequences starting from every number (leads to O(n^2)).
• Forgetting to handle duplicates (set removes them).

Complexity

• Time: O(n) average.
• Extra space: O(n).

Implementation notes (Go)

• Use a set; start only when x-1 is missing.
• Expand forward while x+1 exists.