128. Longest Consecutive Sequence - Solution

128. Longest Consecutive Sequence

Problem Statement

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

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 elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

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

Difficulty

Hard

Solution 1: Sorting

Approach: Sort the array and traverse it. Skip duplicates. If the current number is prev + 1, increment the count; otherwise, reset it. Keep track of the maximum count.

Java

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

C++

class Solution {
public:
    int longestConsecutive(vector& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        sort(nums.begin(), nums.end());
        int ans = 1, t = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == nums[i - 1]) continue;
            if (nums[i] == nums[i - 1] + 1) {
                ans = max(ans, ++t);
            } else {
                t = 1;
            }
        }
        return ans;
    }
};

Python

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

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(log n) or O(n) depending on the language's sorting implementation.

---

Solution 2: Hash Set

Approach: Use a Hash Set for O(1) lookups. For each number, check if it's the start of a sequence (i.e., x - 1 is not in the set). If it is, count how long the sequence continues.

Java

class Solution {
    public int longestConsecutive(int[] nums) {
        Set s = new HashSet<>();
        for (int x : nums) s.add(x);
        int ans = 0;
        for (int x : s) {
            if (!s.contains(x - 1)) {
                int y = x + 1;
                while (s.contains(y)) y++;
                ans = Math.max(ans, y - x);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int longestConsecutive(vector& nums) {
        unordered_set s(nums.begin(), nums.end());
        int ans = 0;
        for (int x : s) {
            if (!s.count(x - 1)) {
                int y = x + 1;
                while (s.count(y)) y++;
                ans = max(ans, y - x);
            }
        }
        return ans;
    }
};

Python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        ans = 0
        for x in s:
            if x - 1 not in s:
                y = x + 1
                while y in s:
                    y += 1
                ans = max(ans, y - x)
        return ans

Time Complexity: O(n) since each element is visited at most twice (once by the loop, once by the while loop).
Space Complexity: O(n) to store the elements in the set.

← All Problems