LeetCode Solution 128 - Longest Consecutive Sequence

Problem Statement:

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], which has length 4.

---

Optimal Approach: Using HashSet

Approach Explanation:

• Store all numbers in an unordered set for quick lookup.
• Iterate through each number, and for each number that is the start of a sequence (num - 1 is not in the set), find the length of the sequence by checking consecutive numbers.
• Keep track of the maximum sequence length found.

C++ Solution:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int longest = 0;
        
        for (int num : numSet) {
            if (numSet.find(num - 1) == numSet.end()) { // Start of a sequence
                int currentNum = num;
                int currentStreak = 1;
                
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                
                longest = max(longest, currentStreak);
            }
        }
        return longest;
    }
};

---

Step-by-Step Execution:

1. Initialization: Store all elements in an unordered set.
2. Identify sequence starts: Iterate through each number and check if it is the start of a sequence.
3. Expand sequence: If num is the start, check for consecutive elements and update the sequence length.
4. Update maximum length: Store the longest sequence found.

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Drawback
Sorting	O(n log n)	O(1)	Sorting takes extra time
Brute Force	O(n²)	O(1)	Checking each sequence individually is too slow
Union-Find	O(n)	O(n)	More complex to implement

Why HashSet is the Best?

• O(n) time complexity with direct lookups.
• Avoids sorting overhead.
• Efficient set-based lookup and iteration.

---

Complexity Analysis:

• Time Complexity: O(n), as each number is checked once.
• Space Complexity: O(n), due to the set storage.

---

Conclusion:

• Best Approach: HashSet-based sequence expansion.
• Key Idea: Use a set to store numbers and efficiently find sequence starts.
• Efficiency: O(n) time complexity with fast lookups.
• Alternative Practice Problems:
  • Number of Islands
  • Pacific Atlantic Water Flow
  • Subarray Sum Equals K

This solution efficiently finds the longest consecutive sequence in an array using an unordered set, making it optimal for large inputs.