LeetCode 128 · Hash Set · Arrays

Longest Consecutive Sequence

MediumFind the longest run of consecutive integers — in O(n), without sorting.
Given an unsorted array of integers nums, return the length of the longest sequence of consecutive integers. The elements do not need to be adjacent in the array. The algorithm must run in O(n) time.

Walkthrough

try:
Find the longest run of consecutive integers (order doesn’t matter). No sorting — a hash set does it in O(n).
hash set
100
4
200
1
3
2
current run
—
best = 0
candidate nin current runprobed (set lookup)
1
function longestConsecutive(nums) {
2
  const set = new Set(nums);
◄
3
  let best = 0;
4
  for (const n of set) {
5
    if (!set.has(n - 1)) {      // n starts a run
6
      let length = 1;
7
      let cur = n;
8
      while (set.has(cur + 1)) {
9
        cur++;
10
        length++;
11
      }
12
      best = Math.max(best, length);
13
    }
14
  }
15
  return best;
16
}
set = {100, 4, 200, 1, 3, 2}
step 0 / 32
line 2
Put every number in a set
Dedupe into a hash set so membership tests (“is x here?”) are O(1).

Intuition

Sorting would make consecutive numbers neighbours, but that costs O(n log n). Instead, drop every number into a hash set so you can test “is x here?” in O(1).

The key insight: only start counting a run from its true beginning. A number n begins a run exactly when n − 1 is NOT in the set — otherwise n is in the middle of some other run and will be counted from that run’s start.

From a run start, walk forward — n, n+1, n+2, … — using set lookups until the next number is missing, tracking the length.

Because each number is only ever walked over as part of the single run it belongs to, the total work is O(n) even though there is a loop inside a loop.

The algorithm

  1. 01Put all numbers into a hash set (this also removes duplicates).
  2. 02For each number n, check if n − 1 is in the set.
  3. 03If it is, skip n — it is not the start of a run.
  4. 04If it is not, walk n, n+1, n+2, … while each is in the set, counting the length.
  5. 05Track the longest length seen and return it.

Reference implementation

1
function longestConsecutive(nums) {
2
  const set = new Set(nums);
3
  let best = 0;
4
  for (const n of set) {
5
    if (!set.has(n - 1)) {          // n starts a run
6
      let length = 1;
7
      let cur = n;
8
      while (set.has(cur + 1)) {
9
        cur++;
10
        length++;
11
      }
12
      best = Math.max(best, length);
13
    }
14
  }
15
  return best;
16
}

Complexity

Time
O(n) — each number is visited at most twice (once by the for-loop, once while extending a run).
Space
O(n) for the hash set.