128_longest_consecutive_sequence.cpp

/*
LeetCode 128 - Longest Consecutive Sequence
Difficulty: Medium

Problem:
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 1:
    Input: nums = [100,4,200,1,3,2]
    Output: 4
    Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Length = 4.

Example 2:
    Input: nums = [0,3,7,2,5,8,1,6,0,4]
    Output: 9

Constraints:
    0 <= nums.length <= 10^5
    -10^9 <= nums[i] <= 10^9

Time Complexity: O(n)
Space Complexity: O(n)
*/

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set(nums.begin(), nums.end());
        int longest = 0;

        for (int num : num_set) {
            // Only start counting from the beginning of a sequence
            if (num_set.find(num - 1) == num_set.end()) {
                int length = 1;
                while (num_set.find(num + length) != num_set.end()) {
                    length++;
                }
                longest = max(longest, length);
            }
        }

        return longest;
    }
};

int main() {
    Solution solution;

    vector<int> nums1 = {100, 4, 200, 1, 3, 2};
    cout << solution.longestConsecutive(nums1) << endl; // 4

    vector<int> nums2 = {0, 3, 7, 2, 5, 8, 1, 6, 0, 4};
    cout << solution.longestConsecutive(nums2) << endl; // 9

    return 0;
}