Algorithm-Day03-Longest-Consecutive-Sequence-lc#128

🧩 Problem Description

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:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4]. Therefore its length is 4.

💡 Brute Force? Not Enough

A naive solution would be to:

• Sort the array → O(n log n)
• Iterate to find longest streak

This fails the O(n) constraint, so we need a better approach.

---

💡 Optimized Approach (Using HashSet)

To achieve linear time:

1. Store all numbers in a HashSet for constant-time lookups.
2. Iterate through the array, and only start a new sequence if num - 1 is not in the set (i.e., it’s the start of a sequence).
3. Expand forward: check how long the consecutive streak goes.
4. Track the max length.

🔢 Java Code

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

        int maxLen = 0;

        for (int num : nums) {
            if (!set.contains(num - 1)) {
                int current = num;
                int length = 1;

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

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

        return maxLen;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Each number is added and checked in constant time.
• Space Complexity: O(n)
  To store all unique numbers in the HashSet.

---

✍️ Summary

• This is a great example of using HashSet to eliminate redundant computation.
• The key optimization is only starting a streak when num - 1 is not in the set.
• Sorting is too slow for this problem — always check time constraints carefully.

This technique of using hash-based lookup to replace sorting is common in many “O(n)” constraint problems.