🔢 Longest Consecutive Sequence

📌 Problem Statement

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

You must solve the algorithm in O(n) time complexity.

---

🧠 Intuition

The first instinct might be to sort the array and check consecutive numbers — but sorting takes O(n log n), which is too slow for this problem.

So how can we find consecutive sequences in O(1) lookup time?

👉 We use a hash set (unordered_set in C++) to:

• Store all numbers for quick access

• Check if a number starts a sequence (i.e., if num - 1 is not in the set)

This helps us ensure each number is processed only once, resulting in an overall O(n) solution.

---

🧩 Logic and Approach

1. Insert all numbers into a hash set.

2. Loop through each number in the set:

   • If num - 1 is not in the set, this is the start of a sequence.

   • From that number, keep checking for num + 1, num + 2, etc.

   • Count how many numbers are in that streak.

3. Update a variable longestLength to keep track of the maximum streak found.

We avoid counting the same sequence multiple times by only starting when the current number has no predecessor (num - 1).

---

✅ C++ Code (Clean & Simple)

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty())
            return 0;

        unordered_set<int> numberSet;
        for (int num : nums) {
            numberSet.insert(num);
        }

        int longestLength = 0;

        for (int num : numberSet) {
            // Only start counting if it's the beginning of a sequence
            if (numberSet.find(num - 1) == numberSet.end()) {
                int currentNum = num;
                int currentLength = 1;

                while (numberSet.find(currentNum + 1) != numberSet.end()) {
                    currentNum += 1;
                    currentLength += 1;
                }

                longestLength = max(longestLength, currentLength);
            }
        }

        return longestLength;
    }
};

---

🔁 Example

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

Explanation:

• The longest consecutive sequence is [1, 2, 3, 4]

• Length = 4

---

🧮 Time & Space Complexity

---

📘 Summary

This is a classic hash-based optimization problem where:

• You avoid sorting

• Use unordered_set to check for sequence continuity

• Only start counting from the beginning of each possible sequence

It’s a perfect example of how to use hashing to speed up search-based logic.

problem link: https://leetcode.com/problems/longest-consecutive-sequence/description/