116. Longest Consecutive Sequence

For each number x, we could count how long the run x, x+1, x+2, … goes. If we do that for every number, we re-walk the same sequence many times. The trick: only count a run when x is the start of its sequence — i.e. when x - 1 is not in the set.

Approach

1. Put all numbers into a set s.
2. For each x in s:
   • If x - 1 in s, skip (not a head).
   • Otherwise walk x, x+1, x+2, … while each is in the set and record the longest run.

Why it's O(n)

Each number is visited by the inner while loop at most once across the whole algorithm, because inner walks only run at sequence heads.

Walk-through

nums = [100, 4, 200, 1, 3, 2] → set {1,2,3,4,100,200}

Heads: 1, 100, 200.

• From 1: 1→2→3→4 length 4.
• From 100: length 1.
• From 200: length 1.

Answer: 4.

import java.util.*;

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) s.add(x);
        int best = 0;
        for (int x : s) {
            if (s.contains(x - 1)) continue;
            int length = 1;
            int y = x + 1;
            while (s.contains(y)) {
                length++;
                y++;
            }
            best = Math.max(best, length);
        }
        return best;
    }
}