Leetcode Study Day 23

Longest Consecutive Sequence

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]. Therefore its length is 4.
Example 2:

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

Constraints:

0 <= nums.length <= 105
-109 <= nums[i] <= 109

My solution

We use the data structure unordered_set to store all the numbers in the array. Then we iterate through the array and check if the number is the start of a consecutive sequence. If it is, we keep checking the next number until we find the end of the sequence. We update the best length if the current length is longer than the best length.

class Solution {
public:
    int longestConsecutive(std::vector<int>& nums) {
        std::unordered_set<int> numSet(nums.begin(), nums.end());
        int best = 0;
        
        for (int n : numSet) {
            if (numSet.find(n - 1) == numSet.end()) {  // only check for one direction
                int m = n + 1;
                while (numSet.find(m) != numSet.end()) {
                    m++;
                }
                best = std::max(best, m - n);
            }
        }
        
        return best;
    }
};