Longest consecutive sequence

Hard TimeO(n) SpaceO(n)

Given an unsorted array nums, return the length of the longest run of consecutive integers it contains — for [100, 4, 200, 1, 3, 2] that is 4, the run 1, 2, 3, 4. Values may repeat, and a run does not have to appear in order.

Examples

Example 1

Input
nums = [100, 4, 200, 1, 3, 2]
Output
4
1, 2, 3, 4 is the longest run; 100 and 200 stand alone.

Example 2

Input
nums = [7, 7, 7]
Output
1
There is only one distinct value, so the longest run is 7 by itself.

The Code

function longestConsecutive(nums) {
  const values = new Set(nums);
  let best = 0;
  for (let i = 0; i < nums.length; i++) {
    const n = nums[i];
    if (values.has(n - 1)) continue;
    let length = 1;
    while (values.has(n + length)) {
      length++;
    }
    if (length > best) best = length;
  }
  return best;
}
longestConsecutive([100, 4, 200, 1, 3, 2]);
Done
Step through longestConsecutive([100, 4, 200, 1, 3, 2]) call by call

Explanation

A run of consecutive numbers can be counted by starting at its lowest member and asking, again and again, whether the next number up is present — which a set answers at once. Counting only from a run’s lowest member is what makes it cheap: any number with its predecessor also present is inside a run someone else will count, so it is passed over. Every number is therefore considered once as a possible start, and walked over once more only inside the single run it belongs to.

  1. 1

    At i = 0, n is 100. values.has(99) is false, so nothing sits below it and a run starts here — but values.has(101) is false too, so the run is 100 by itself and best takes its length.

    i
    100
    0
    4
    1
    200
    2
    1
    3
    3
    4
    2
    5

    best=0

    run from 100 → length 1 · best = 1

  2. 2

    At i = 1, n is 4 and values.has(3) is true. 4 is inside a run rather than at the start of one, so continue skips it and nothing is counted.

    100
    0
    i
    4
    1
    200
    2
    1
    3
    3
    4
    2
    5

    best=1

    has(3)? yes → skip

  3. 3

    At i = 2, n is 200. Nothing sits below it either, so a run starts — and stops at once, since there is no 201. A length of 1 does not beat best.

    100
    0
    4
    1
    i
    200
    2
    1
    3
    3
    4
    2
    5

    best=1

    run from 200 → length 1 · best stays 1

  4. 4

    At i = 3, n is 1, and values.has(0) is false — so this is the start of a real run, and counting begins.

    100
    0
    4
    1
    200
    2
    i
    1
    3
    3
    4
    2
    5

    best=1

    has(0)? no → count from 1

  5. 5

    values.has(2), then has(3), then has(4) are all true, so length climbs with each one. has(5) is false and the climb stops at 4, which best takes.

    100
    0
    4
    1
    200
    2
    i
    1
    3
    3
    4
    2
    5

    best=1length=3

    length → 4 · best = 4

  6. 6

    The last two numbers, the 3 and the 2, both have predecessors in values, so both are skipped — the run they belong to has already been counted once, from its own start. best is returned.

    100
    0
    4
    1
    200
    2
    1
    3
    3
    4
    i
    2
    5

    best=4

    return 4

More like this

All arrays & loops examples (10) →