LeetCode 128 · Medium · Arrays & Hashing

Longest Consecutive Sequence

Given an unsorted integer array nums, return the length of the longest run of consecutive values (like 1, 2, 3, 4) that all appear in it. The run can use the values in any order, and the solution must beat sorting: O(n).

O(n)time
O(n)space · the set
n − 1 ∉ setonly starts count up

0–16 integers, −99 to 99 · duplicates allowed

the set is empty

numSet on a number line sorted only for display · … marks a missing value · solid = current run · dashed = longest so far

public int longestConsecutive(int[] nums) { Set<Integer> numSet = new HashSet<>(); for (int n : nums) { numSet.add(n); } int longest = 0; for (int n : numSet) { if (!numSet.contains(n - 1)) { // n starts a run int length = 1; while (numSet.contains(n + length)) { length++; } longest = Math.max(length, longest); } } return longest;}
n
—
contains(n − 1)
—
length
—
longest
0
numSet
—

Why it works

  1. Brute force counts up from every value: O(n²) set lookups, or O(n³) with a list. Sorting first and scanning for runs is O(n log n).
  2. Only start at a start. A value n begins a run exactly when n − 1 is missing. Every other value sits inside some run that its start will count, so it is skipped in O(1).
  3. Why O(n): the inner while only runs from starts, and each value is stepped over by at most one start's count. Total lookups: about 2 per value. The set costs O(n) space.
  4. Pitfall: loop over the set, not over nums. With many copies of a start value, looping over nums recounts the same run for each copy.
  5. Order does not matter. A HashSet is visited in whatever order it holds its values (the order is not guaranteed); a non-start can come before or after its start and the answer is the same.