Longest Consecutive Sequence

The problem

Given a list of integers nums in no particular order, find the longest run of consecutive values, such as 1, 2, 3, 4, that can be built from the values in the list, and return its length. The values of a run do not have to sit next to each other in the list. A repeated value counts once. An empty list returns 0. Aim for a method that takes O(n) time.

What to write

function solve(nums: number[]): number

Input
nums = [100,4,200,1,3,2]

Output
4

Input
nums = [0,3,7,2,5,8,4,6,0,1]

Output
9

Constraints

0–10,000 integers within ±1,000,000; duplicates allowed.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   You are asked for O(n) time. Sorting takes about n log n steps, so the plan of sorting the values and then scanning them misses that target. You need to find the runs without putting the values in order.

2. Hint 2: Ask a smaller question

   Look at the value 3 in the list 100, 4, 200, 1, 3, 2. How could you tell, without sorting, whether 3 is the first value of its run or somewhere in the middle of it?

3. Hint 3: Name the pattern

   A value starts a run exactly when the value one below it is missing. To ask "is this value in the list?" in one step, put all the values in a hash set first. This is hash set membership. Read the lesson on hash set membership.

4. Hint 4: State the invariant

   Counting begins only at the first value of a run. Every run has exactly one first value, so every run is counted once and each value is walked over at most once in all the counting.

5. Hint 5: Sketch the pseudocode

   Put all values in a set. For each value in the set: if the value minus 1 is in the set, skip it. Otherwise count upward, value plus 1, value plus 2, and so on, while each is in the set. Remember the longest count.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Put values in a Set. Start counting only at values with no predecessor, ensuring each consecutive run is scanned once.

The slow way

Sort the values and scan them once, counting how long each stretch of consecutive values lasts. It is correct and simple, but sorting takes about n log n steps and the task asks for O(n).

The insight

You do not need the values in order to find a run. You only need to recognize where a run starts, at a value whose predecessor (the value one below it) is missing, and then to check whether the next value exists. A hash set answers both in one step.

Step by step

1. Put every value in a set so any value can be found in one step. The set makes "is this value in the list?" a one-step question, and it also drops the repeated values, which never lengthen a run.
2. Skip a value whose predecessor exists: it is not the start of a run. A value with a predecessor is in the middle of a run that will be counted from its real start. Counting it again would be wasted work.
3. From a start, walk up while the next value exists. Starting from the first value of a run, each next value either exists, and the run goes on, or it does not, and the run ends here.
4. Keep the longest run found so far. A run from its first value to its last holds last minus first plus one values. The largest such length is the answer.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Put every value in a set so any value can be found in one step
  const set = new Set(nums);
  let best = 0;
  for (const n of set) {
    // 2. Skip a value whose predecessor exists: it is not the start of a run
    if (set.has(n - 1)) continue;
    // 3. From a start, walk up while the next value exists
    let end = n;
    while (set.has(end + 1)) end++;
    // 4. Keep the longest run found so far
    best = Math.max(best, end - n + 1);
  }
  return best;
}

function solve(nums: number[]): number {
  // 1. Put every value in a set so any value can be found in one step
  const set = new Set(nums);
  let best = 0;
  for (const n of set) {
    // 2. Skip a value whose predecessor exists: it is not the start of a run
    if (set.has(n - 1)) continue;
    // 3. From a start, walk up while the next value exists
    let end = n;
    while (set.has(end + 1)) end++;
    // 4. Keep the longest run found so far
    best = Math.max(best, end - n + 1);
  }
  return best;
}

def solve(nums):
    # 1. Put every value in a set so any value can be found in one step
    num_set = set(nums)
    best = 0
    for num in num_set:
        # 2. Skip a value whose predecessor exists: it is not the start of a run
        if num - 1 in num_set:
            continue
        # 3. From a start, walk up while the next value exists
        end = num
        while end + 1 in num_set:
            end += 1
        # 4. Keep the longest run found so far
        best = max(best, end - num + 1)
    return best

Example 1, traced

Input
nums = [100,4,200,1,3,2]

Output
4

Why it works

Every run of consecutive values has exactly one value whose predecessor is missing, its first. Counting upward from that value visits the whole run and stops at its end, so every run's full length is measured once, and the largest one is kept.

Time and space

Time O(n) expected, extra space O(n). Building the set takes n steps. Counting only starts at the first value of a run, so over the whole loop each value is stepped over at most once: O(n) in total, "expected" because a set lookup takes one step on average. The set holds up to n values.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Keep the check for a predecessor. The answer stays right without it, but a list such as 1, 2, 3 up to n recounts the run from every value and takes about n × n / 2 steps.
• Loop over the set, not the original list. A list with many copies of one starting value would count the same run once per copy.
• A run from first to last holds last minus first plus one values. Forgetting the plus one makes the answer one too small for every list that is not empty.

Pattern

Hash set membership. Builds on Contains Duplicate.

Keep going