Longest Consecutive Sequence

Medium Problem 11 of 151 Java and Python

Problem

Given an unsorted array of integers nums, return the length of the longest sequence of consecutive integers (such as 4, 5, 6, 7) that can be formed from its elements.

The algorithm must run in O(n) time.

Example 1

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

Example 2

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

Constraints

0 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Explanation

Sorting would put runs next to each other, but costs O(n log n).

With a hash set you can ask "is x - 1 present?" in O(1). If it is not, x is the start of a run, so count upwards x + 1, x + 2, … Each number is visited at most twice in total, which keeps it O(n).

Approach 1 · Naive

Sort and scan

Time O(n log n)
Space O(1) extra

Sort the numbers, then walk through them, extending the current run when the next number is one larger and skipping duplicates.

If the array is empty, return 0.
Sort it. Keep current = 1 and best = 1.
For each next number: if it equals the previous one, skip; if it is previous + 1, extend current; otherwise reset current to 1.
Track the maximum current.

Java

import java.util.*;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int best = 1;
        int current = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            current = nums[i] == nums[i - 1] + 1 ? current + 1 : 1;
            best = Math.max(best, current);
        }
        return best;
    }
}

Python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        nums.sort()
        best = current = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                continue
            current = current + 1 if nums[i] == nums[i - 1] + 1 else 1
            best = max(best, current)
        return best

Approach 2 · Optimal

Hash set, count from run starts

Time O(n)
Space O(n)

Put every number in a set. Only start counting at numbers whose predecessor is missing, then walk forward while the next number exists.

Add all numbers to a set.
For each number x in the set: skip it if x - 1 is in the set.
Otherwise count length while x + length is in the set.
Return the longest length found.

Java

import java.util.*;

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int best = 0;
        for (int x : set) {
            if (set.contains(x - 1)) {
                continue;
            }
            int length = 1;
            while (set.contains(x + length)) {
                length++;
            }
            best = Math.max(best, length);
        }
        return best;
    }
}

Python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numbers = set(nums)
        best = 0
        for x in numbers:
            if x - 1 in numbers:
                continue
            length = 1
            while x + length in numbers:
                length += 1
            best = max(best, length)
        return best

Complexity compared

Approach	Time	Space
Naive Sort and scan	O(n log n)	O(1) extra
Optimal Hash set, count from run starts	O(n)	O(n)

Key takeaways

The "only start at the beginning of a run" check is what turns a nested loop into O(n).
Loop over the set, not the array, so duplicates do not repeat work.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem