128. Longest Consecutive Sequence

• Link: https://leetcode.com/problems/longest-consecutive-sequence

Question

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.

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

Example 3:

Input: nums = [1,0,1,2]
Output: 3

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

Approach 1: Brute Force

Intuition

• If we sort the array, consecutive numbers will be next to each other.
• We walk the sorted list and count lengths of consecutive runs.
• Ignore duplicates.
• Track the longest streak seen.

Algorithm

1. If nums is empty → return 0.
2. Sort nums.
3. Initialize:
   • curr = 1 (current streak)
   • best = 1 (longest streak)
4. For each element from index 1 to n-1:
   • If equal to previous → skip (duplicate)
   • If nums[i] == nums[i-1] + 1 → extend streak (curr++)
   • Else → reset streak (curr = 1)
   • Update best = max(best, curr)
5. Return best.

Code

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

        int longest = 1;
        int curr = 1;

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

            if (nums[i] == nums[i - 1] + 1) {
                curr++;
            } else {
                curr = 1;
            }
            longest = max(longest, curr);
        }    

        return longest;
    }
};

Complexity Analysis

• Time Complexity: $O(NLog(N))$
• Space Complexity: $O(1)$

Approach 2: Better

Intuition

• Every consecutive sequence must start at a number whose previous number is NOT in the set.
• For each number that qualifies as a “start,” count how long the streak continues.
• Each number is processed at most once → O(n).

Algorithm

1. Insert all numbers into an unordered_set.
2. For each num in the set:
   • If (num - 1) exists, skip it (not a start).
   • Otherwise:
     • This is a start → count how many consecutive integers exist:
       num, num+1, num+2, ...
     • Update the longest streak.
3. Return the longest streak.

Code

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;

        unordered_set<int> s(nums.begin(), nums.end());
        int longest = 0;

        for (int num : s) {
            // Only start counting from the beginning of a sequence
            if (s.count(num - 1) == 0) {
                int curr = num;
                int streak = 1;

                while (s.count(curr + 1)) {
                    curr++;
                    streak++;
                }

                longest = max(longest, streak);
            }
        }

        return longest;
    }
};

Complexity Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$