Longest Consecutive Sequence

medium
Arrays & HashingArrayHash TableUnion-Find

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. A consecutive sequence is one where each element is exactly 1 more than the previous element (e.g., [1, 2, 3, 4]).

You must write an algorithm that runs in O(n) time.

Examples

Example 1

  • Input: nums = [100,4,200,1,3,2]
  • Output: 4
  • Explanation: The longest consecutive sequence is [1, 2, 3, 4] with length 4.

Example 2

  • Input: nums = [0,3,7,2,5,8,4,6,0,1]
  • Output: 9
  • Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8] with length 9.

Example 3

  • Input: nums = []
  • Output: 0

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Sorting

Intuition

A straightforward approach is to sort the array first. Once sorted, consecutive numbers will be adjacent. We scan through the sorted array, counting the length of each consecutive run while skipping duplicates. This does not meet the O(n) requirement but is simple to implement and easy to understand.

Algorithm

  1. If the array is empty, return 0.
  2. Sort the array.
  3. Initialize longest to 1 and currentStreak to 1.
  4. Iterate from index 1 to n-1. If nums[i] == nums[i-1], skip (duplicate). If nums[i] == nums[i-1] + 1, increment currentStreak. Otherwise, reset currentStreak to 1.
  5. Update longest with the maximum of longest and currentStreak at each step.
  6. Return longest.
TimeO(n log n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        sort(nums.begin(), nums.end());

        int longest = 1;
        int currentStreak = 1;

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) continue;
            if (nums[i] == nums[i - 1] + 1) {
                currentStreak++;
            } else {
                currentStreak = 1;
            }
            longest = max(longest, currentStreak);
        }

        return longest;
    }
};
Java 21
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Arrays.sort(nums);

        int longest = 1;
        int currentStreak = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) continue;
            if (nums[i] == nums[i - 1] + 1) {
                currentStreak++;
            } else {
                currentStreak = 1;
            }
            longest = Math.max(longest, currentStreak);
        }

        return longest;
    }
}
Python 3.12
def longestConsecutive(nums: list[int]) -> int:
    if not nums:
        return 0
    nums.sort()

    longest = 1
    current_streak = 1

    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            continue
        if nums[i] == nums[i - 1] + 1:
            current_streak += 1
        else:
            current_streak = 1
        longest = max(longest, current_streak)

    return longest
Go 1.26
import "sort"

func longestConsecutive(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    sort.Ints(nums)

    longest := 1
    currentStreak := 1

    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[i-1] {
            continue
        }
        if nums[i] == nums[i-1]+1 {
            currentStreak++
        } else {
            currentStreak = 1
        }
        if currentStreak > longest {
            longest = currentStreak
        }
    }

    return longest
}
Approach 2

Hash Set

Intuition

The optimal approach uses a hash set for O(1) lookups. First, insert all numbers into a set. Then, for each number, check if it is the start of a sequence (i.e., num - 1 is not in the set). If it is a sequence start, count how many consecutive numbers follow by checking num + 1, num + 2, and so on. This ensures each element is visited at most twice (once during insertion, once during counting), giving O(n) overall time.

Algorithm

  1. Insert all numbers into a hash set.
  2. Initialize longest to 0.
  3. For each number in the set, check if num - 1 exists in the set. If it does, skip this number (it is not the start of a sequence).
  4. If num - 1 does not exist, this is the start of a sequence. Count consecutive elements by checking num + 1, num + 2, etc.
  5. Update longest with the length of the current sequence.
  6. Return longest.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int longest = 0;

        for (int num : numSet) {
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;
                    currentStreak++;
                }

                longest = max(longest, currentStreak);
            }
        }

        return longest;
    }
};
Java 21
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int longest = 0;

        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }

                longest = Math.max(longest, currentStreak);
            }
        }

        return longest;
    }
}
Python 3.12
def longestConsecutive(nums: list[int]) -> int:
    num_set = set(nums)
    longest = 0

    for num in num_set:
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            longest = max(longest, current_streak)

    return longest
Go 1.26
func longestConsecutive(nums []int) int {
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }

    longest := 0

    for num := range numSet {
        if !numSet[num-1] {
            currentNum := num
            currentStreak := 1

            for numSet[currentNum+1] {
                currentNum++
                currentStreak++
            }

            if currentStreak > longest {
                longest = currentStreak
            }
        }
    }

    return longest
}

Frequently asked questions

What is the optimal time complexity of Longest Consecutive Sequence?

The most efficient approach in this guide ("Hash Set") runs in O(n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Longest Consecutive Sequence use?

Longest Consecutive Sequence is a medium-level Arrays & Hashing problem involving Array, Hash Table, Union-Find. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Longest Consecutive Sequence be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
nums=
[100,4,200,1,3,2]
Expected Output
4