LeetCode Study Note | Problem 128: Longest Consecutive Sequence

📌 Problem Summary

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

Time complexity must be O(n).

Example Input:

[0,3,7,2,5,8,4,6,0,1]

Expected Output:

9 (i.e., the sequence [0,1,2,3,4,5,6,7,8])

🧪 Initial Attempt (Incorrect)

public int longestConsecutive(int[] nums) {
    HashSet<Integer> objects = new HashSet<>();
    for (int item : nums) {
        objects.add(item);
    }
    List<Integer> collect = objects.stream().sorted().toList();

    if (objects.isEmpty()) return 0;
    if (objects.size() < 2) return 1;

    int max = 1;
    int len = 1;

    for (int i = 1; i < collect.size(); i++) {
        if (collect.get(i) == collect.get(i - 1) + 1) {
            len++;
        } else {
            max = Math.max(max, len);
            len = 1;
        }
    }
    return max;  // ⚠️ Bug here
}

🐞 Bug Analysis

1. Final Segment Not Counted:

   • If the longest sequence is at the end (like [0,1,2,3,4,5,6,7,8]), it doesn’t update max after the loop finishes.

2. Time Complexity Violation:

   • Using .stream().sorted() leads to O(n log n), which violates the problem’s O(n) constraint.

✅ Fixed Version (Still 

O(n log n)

)

public int longestConsecutive(int[] nums) {
    HashSet<Integer> objects = new HashSet<>();
    for (int item : nums) {
        objects.add(item);
    }
    List<Integer> collect = objects.stream().sorted().toList();

    if (objects.isEmpty()) return 0;
    if (objects.size() < 2) return 1;

    int max = 1;
    int len = 1;

    for (int i = 1; i < collect.size(); i++) {
        if (collect.get(i) == collect.get(i - 1) + 1) {
            len++;
        } else {
            max = Math.max(max, len);
            len = 1;
        }
    }
    max = Math.max(max, len);  // ✅ Final update to fix the bug

    return max;
}

🚀 Optimal Solution (O(n) Time)

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }

    int longest = 0;

    for (int num : set) {
        // Only start counting if num is the beginning of a sequence
        if (!set.contains(num - 1)) {
            int current = num;
            int length = 1;

            while (set.contains(current + 1)) {
                current++;
                length++;
            }

            longest = Math.max(longest, length);
        }
    }

    return longest;
}

💡 Key Takeaways