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.

Why this is worth learning

A set removes duplicates, but linear time also requires iterating distinct starts. Walking from every copy of the same minimum value repeats a whole run.

Before coding: one-minute experiment

For [1,1,1,2,3,4], how many times should the length-four run be expanded?

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 distinct key x in the set, rather than each occurrence in the original input:
   • 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

Partition the distinct input values into maximal consecutive runs. A value is a run start exactly when its predecessor is absent. Starting a forward walk only at such a value visits all and only the members of its run, so its measured length is correct. Distinct runs are disjoint and every run has exactly one start. Iterating set keys, rather than the original duplicate-containing slice, ensures each run is walked only once. The largest measured run is therefore the requested answer, with at most a constant number of expected-time set probes per distinct value plus initial input insertion.

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
- 2,3,4 are not starts because their predecessors are present
- 100 and 200 are also starts, each giving a run of length 1
- set iteration order is unspecified; best is 4 in any order

Pitfalls to avoid

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

Debugging lens

An adversarial input contains many copies of a run minimum followed by one long consecutive run. Random small arrays rarely reveal this complexity bug. A sorted-distinct oracle provides an independent correctness check.

Complexity

Expected time: O(n) for n input occurrences: build the set once and expand each distinct run once. Auxiliary space: O(u) for u distinct values.

Implementation notes (Go)

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

Reconstruction checkpoint

For [1,1,1,2,3,4], how many times should the length-four run be expanded?

Return to Hash Map · Module quiz