Longest Consecutive Sequence

Problem Statement

You’re an explorer in an unsorted array of integers, seeking the longest chain of consecutive numbers. This medium-level set challenge is a sequence scavenger hunt—use hashing to connect the dots in one pass!

Example

Input: nums = [100, 4, 200, 1, 3, 2]

Output: 4 ([1, 2, 3, 4])

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

Output: 9 ([0, 1, 2, 3, 4, 5, 6, 7, 8])

Input: nums = []

Output: 0

Code

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

def longest_consecutive(nums):
    num_set = set(nums)
    max_len = 0
    for num in nums:
        if num - 1 not in num_set:
            curr = num
            curr_len = 1
            while curr + 1 in num_set:
                curr += 1
                curr_len += 1
            max_len = max(max_len, curr_len)
    return max_len
            

function longestConsecutive(nums) {
    let set = new Set(nums);
    let maxLen = 0;
    for (let num of nums) {
        if (!set.has(num - 1)) {
            let curr = num;
            let len = 1;
            while (set.has(curr + 1)) {
                curr++;
                len++;
            }
            maxLen = Math.max(maxLen, len);
        }
    }
    return maxLen;
}
            

Explanation

• Set Insight: Use a set for O(1) lookups to find sequence starts.
• Flow: Only start counting from the smallest number in a sequence (no num-1 in set).
• Example Walkthrough: [100,4,200,1,3,2] → start at 1, count 1,2,3,4 → 4.
• Optimization: Skip numbers that aren’t sequence starts—saves time.
• Edge Case: Empty array or duplicates handled seamlessly.

Note