128. Longest Consecutive Sequence

Given an unsorted array, return the length of the longest run of consecutive integers. Aim for O(n) time.

Put everything in a set. Only start counting at x when x − 1 is absent (x starts a run), then walk x+1, x+2, … Each number is visited a constant number of times.

1function longestConsecutive(nums: number[]): number {
2  const set = new Set(nums);
3  let best = 0;
4  for (const x of set) {
5    if (set.has(x - 1)) continue;
6    let len = 1;
7    while (set.has(x + len)) len++;
8    best = Math.max(best, len);
9  }
10  return best;
11}

best = 0

set

100

200

Put every number in a set.

1 / 0

Space: play/pause · ←/→: step