---

1. Problem Summary

You are given an unsorted integer array nums.

Your task is to find the length of the longest consecutive sequence, where:

• A consecutive sequence contains integers that follow each other: x, x+1, x+2, ...
• Order in the array does NOT matter
• Elements do not have to be adjacent
• You must return only the length, not the sequence

Example:

Input:  [100, 4, 200, 1, 3, 2]
Consecutive sequence: 1,2,3,4
Output: 4

---

2. Key Insights

Insight 1: Sorting works, but too slow

Sorting takes:

O(N log N)

But we need an O(N) solution.

Insight 2: HashSet enables O(1) lookups

If values are stored in a HashSet, we can quickly check if neighbors exist.

Insight 3: Only start counting when sequence begins

A number x starts a sequence only if:

x - 1 is not in the set

This ensures each sequence is counted once.

Insight 4: Then count forward

From starting number, increment:

x+1, x+2, x+3 ...

until numbers stop appearing.

Insight 5: Track max length

Update as longest chain discovered.

---

3. Approach

HashSet + linear scan for sequence starts

Steps:

1. Insert all numbers into a HashSet
2. Initialize longest = 0
3. Loop through nums:
   • If (num - 1) not in set, this is start of a sequence
   • Count how many consecutive numbers follow
   • Update longest
4. Return longest

---

4. Time and Space Complexity

Time Complexity:

O(N)

Each number checked at most twice.

Space Complexity:

O(N)

HashSet storage.

---

5. Java Solution

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for (int num : nums) {
            set.add(num);
        }

        int longest = 0;

        for (int num : nums) {
            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;
    }
}

---

6. Dry Run Examples

Example 1

Input:

[100, 4, 200, 1, 3, 2]

Set = {1,2,3,4,100,200}

Sequence starts:

• 100 → length 1
• 4 not start (3 exists)
• 200 → length 1
• 1 → count 1,2,3,4 → length 4

Output:

4

---

Example 2

Input:

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

Longest chain:

0,1,2,3,4,5,6,7,8  → length 9

Output:

9

---

Example 3

Input:

[]

Output:

0

---

Example 4

Input:

[9]

Output:

1

---

Example 5

Input:

[1,2,0,1]

Set = {0,1,2}
Longest = 3

Output:

3

---

7. Why This Solution Works

• HashSet ensures O(1) neighbor lookup
• Only counts sequence once, at proper start
• Avoids sorting overhead
• Handles duplicates implicitly
• Works for:
  • negative numbers
  • unsorted values
  • scattered ranges

---

8. Common Mistakes

1. Sorting unnecessarily (O(N log N))
2. Counting sequences from every number instead of starts
3. Forgetting duplicates waste iteration
4. Using map incorrectly for frequency
5. Missing edge case empty array