Problem #128: Longest Consecutive Sequence

Intuition & Strategy Breakdown

Store numbers in a hash set. For each number x, check if (x - 1) exists in set; if not, x is the start of a sequence. Count consecutive numbers (x+1, x+2...).

Python Solution

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        longest = 0

        for n in nums:
            # Check if it's the start of a sequence
            if (n - 1) not in num_set:
                length = 1
                while (n + length) in num_set:
                    length += 1
                longest = max(length, longest)
        
        return longest

Java Solution

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