Question

How to find the length of the longest consecutive sequence of an unsorted vector of integers in C++

Answer 1

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

int longestConsecutive(std::vector<int>& nums) {
    std::unordered_set<int> numSet(nums.begin(), nums.end());
    int longestStreak = 0;

    for (int num : numSet) {
        // Check if it's the start of a sequence
        if (numSet.find(num - 1) == numSet.end()) {
            int currentNum = num;
            int currentStreak = 1;

            // Count the length of the sequence
            while (numSet.find(currentNum + 1) != numSet.end()) {
                currentNum++;
                currentStreak++;
            }

            longestStreak = std::max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}

int main() {
    std::vector<int> nums = {680, 4, 590, 3, 1, 2};
    
    std::cout << "Length of the longest consecutive sequence: " << longestConsecutive(nums) << "\n";
}



/*
run:

Length of the longest consecutive sequence: 4

*/

 

70+ SQL courses for beginners and professionals