9. Longest Consecutive Sequence

Description

Longest Consecutive Sequence
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

Constraints:

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

Approach 1

• Store the original nums in a Set
• Then iterate through it check if element-1 exist if it does not that means it is a start of a new sequence then keep checking if +1 exists adding to the count then find the max
• One way to make it even more optimized is to check if the longest sequence is greater then half of the input size because there can not be a sequence bigger than this

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
 
        Set<Integer> numbers = new HashSet<>();
        int longest = 1;
 
        for (int num: nums) {
            numbers.add(num);
        }
 
        for(int num: nums) {
            if(!numbers.contains(num-1)) {
                int count = 1;
                while(numbers.contains(num+1)) {
                    count++;
                    num++;
                }
                longest = Math.max(longest,count);
            }
 
            if(longest > nums.length/2) break;
        }
 
        return longest;
    }
}

Brute Force Approach: Sorting

Intuition
Sort the array so consecutive numbers appear next to each other. Traverse the sorted array, ignore duplicates, and increment a running sequence count whenever the current number is exactly $1$ greater than the previous number.

import java.util.Arrays;
 
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        
        Arrays.sort(nums);
        
        int maxStreak = 1;
        int currentStreak = 1;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) { // Skip duplicate values
                if (nums[i] == nums[i - 1] + 1) {
                    currentStreak++;
                } else {
                    maxStreak = Math.max(maxStreak, currentStreak);
                    currentStreak = 1;
                }
            }
        }
        
        return Math.max(maxStreak, currentStreak);
    }
}
 

• Time Complexity: $O(n\log n)$ due to the sorting step.
• Space Complexity: $O(1)$ or $O(n)$ depending on the language’s built-in sorting implementation.

---

Most Optimized Approach: HashSet (Sequence Start Check)

Intuition & Memory Trick
To achieve $O(n)$ time, store all numbers in a HashSet for $O(1)$ lookups. The key trick to keep it $O(n)$ and easy to remember: only count forward if a number is the start of a sequence.

• How to identify a sequence start: A number x is a start only if x - 1 is not in the set.
• If x - 1 exists, skip x because it will be processed when the loop reaches the actual start of its chain.
• This is the same solution just iterate over set instead of array to save time from duplication

import java.util.HashSet;
import java.util.Set;
 
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
 
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
 
        int maxStreak = 0;
 
        // Iterate over unique elements in numSet (handles duplicates efficiently)
        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
 
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
 
                maxStreak = Math.max(maxStreak, currentStreak);
 
                // Early exit optimization
                if (maxStreak > nums.length / 2) {
                    break;
                }
            }
        }
 
        return maxStreak;
    }
}

• Time Complexity: $O(n)$ — The inner while loop only runs for sequence starters, so each number is processed at most twice in total.
• Space Complexity: $O(n)$ to store elements in the hash set.