Optimize the code · Medium

Speed Up Longest Consecutive Sequence

Medium Make it fast Most askedSeen at Google, Amazon, Meta

longestConsecutive(nums) returns the length of the longest run of consecutive integers that can be formed from the values in nums (in any order). For example [100, 4, 200, 1, 3, 2] contains 1, 2, 3, 4, so the answer is 4.

The version below is correct but searches the whole array for every next number. Make it O(n) without changing the results.

Example 1

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

Example 2

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

The slow code

Every case must finish within 300 ms (budgets are per language in the editor).

function longestConsecutive(nums) {
  let best = 0;
  for (const x of nums) {
    let length = 1;
    let next = x + 1;
    while (nums.includes(next)) {
      length++;
      next++;
    }
    best = Math.max(best, length);
  }
  return best;
}

function longestConsecutive(nums: number[]): number {
  let best = 0;
  for (const x of nums) {
    let length = 1;
    let next = x + 1;
    while (nums.includes(next)) {
      length++;
      next++;
    }
    best = Math.max(best, length);
  }
  return best;
}

def longest_consecutive(nums: list[int]) -> int:
    best = 0
    for x in nums:
        length, nxt = 1, x + 1
        while nxt in nums:
            length += 1
            nxt += 1
        best = max(best, length)
    return best

<?php

function longestConsecutive(array $nums): int
{
    $best = 0;
    foreach ($nums as $x) {
        $length = 1;
        $next = $x + 1;
        while (in_array($next, $nums, true)) {
            $length++;
            $next++;
        }
        $best = max($best, $length);
    }
    return $best;
}

class Solution {
    public int longestConsecutive(int[] nums) {
        int best = 0;
        for (int x : nums) {
            int length = 1;
            int next = x + 1;
            while (contains(nums, next)) {
                length++;
                next++;
            }
            best = Math.max(best, length);
        }
        return best;
    }

    private boolean contains(int[] nums, int v) {
        for (int x : nums) if (x == v) return true;
        return false;
    }
}

Hints

Hint 1

Replace the array search with a set lookup.

Hint 2

Only start counting from x when x - 1 is not in the set: then each run is walked exactly once.

Make it faster

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Why it is slow: every includes(x + 1) scans the whole array, and the loop starts a new walk from every element, so long runs are walked again from each of their members: O(n^2) or worse.

The fix: put the values in a hash set. For each value x, start a walk only if x - 1 is not in the set (so x begins a run), then count x + 1, x + 2, ... with O(1) lookups. Each value is visited by at most one walk, so the total is O(n).

Sorting first (O(n log n)) is a fine answer to mention, but the interviewer asking this question is looking for the O(n) set trick.

Optimized solution

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue; // not the start of a run
    let y = x;
    while (set.has(y + 1)) y++;
    best = Math.max(best, y - x + 1);
  }
  return best;
}

function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue; // not the start of a run
    let y = x;
    while (set.has(y + 1)) y++;
    best = Math.max(best, y - x + 1);
  }
  return best;
}

def longest_consecutive(nums: list[int]) -> int:
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 in values:
            continue  # not the start of a run
        y = x
        while y + 1 in values:
            y += 1
        best = max(best, y - x + 1)
    return best

<?php

function longestConsecutive(array $nums): int
{
    $set = array_flip($nums);
    $best = 0;
    foreach ($set as $x => $_) {
        if (isset($set[$x - 1])) {
            continue; // not the start of a run
        }
        $y = $x;
        while (isset($set[$y + 1])) {
            $y++;
        }
        $best = max($best, $y - $x + 1);
    }
    return $best;
}

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int best = 0;
        for (int x : set) {
            if (set.contains(x - 1)) continue; // not the start of a run
            int y = x;
            while (set.contains(y + 1)) y++;
            best = Math.max(best, y - x + 1);
        }
        return best;
    }
}

Common mistakes

Starting a walk from every element: still O(n^2) in the worst case (one long run).
Not handling duplicates or the empty array.

Follow-up questions

Return the run itself, not its length.
Values arrive one by one: maintain the answer with union-find.

Speed Up Contains Duplicate · Easy
Speed Up Two Sum · Easy
Speed Up Recursive Fibonacci · Easy
Speed Up the Most Frequent Word · Easy
Speed Up the Active-Customer Join · Easy
Speed Up Range Sum Queries · Medium