Coding problem · Medium · Arrays & Hashing

Longest Consecutive Sequence

Medium Algorithms & data structures Seen at Google, Amazon, Spotify

Given an unsorted array of integers nums, return the length of the longest sequence of consecutive values (e.g. 1,2,3,4). Your algorithm must run in O(n) time.

Example 1

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The sequence is 1, 2, 3, 4.

Example 2

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

Constraints

0 <= nums.length <= 10^5

Hints

Hint 1

Sorting is O(n log n). Put everything in a set.

Hint 2

Only start counting from numbers that begin a sequence: x where x−1 is not in the set.

Write and run your solution

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

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Load the values into a set. For each value that has no predecessor (x - 1 missing), walk forward while x + 1, x + 2, … exist. Each value is visited at most twice, so the whole thing is linear.

Reference solution

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue;
    let len = 1;
    while (set.has(x + len)) len++;
    best = Math.max(best, len);
  }
  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;
    let len = 1;
    while (set.has(x + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

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

<?php

function longestConsecutive(array $nums): int
{
    $set = array_flip($nums);
    $best = 0;
    foreach ($set as $x => $_) {
        if (isset($set[$x - 1])) {
            continue;
        }
        $len = 1;
        while (isset($set[$x + $len])) {
            $len++;
        }
        $best = max($best, $len);
    }
    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;
            int len = 1;
            while (set.contains(x + len)) len++;
            best = Math.max(best, len);
        }
        return best;
    }
}