Interview Classic 150 Questions P128 Longest Consecutive Sequence

---

Timeline

timeline

2025-11-14

init

hash table

---

Title:

P128 Longest Consecutive Sequence

https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-interview-150

Using a hash table, although there is a while loop inside the for loop, overall each element is visited only once. The core idea is to find the minimum of each consecutive sequence each time, and then sequentially find the consecutive elements after this sequence. Note that when traversing, you should traverse the uset to avoid too many duplicate elements when traversing nums.

#include <vector>
#include <unordered_set>

using std::unordered_set;
using std::vector;

class Solution {
    public:
        int longestConsecutive(vector<int> &nums)
        {
                int curr, longest = 0;
                unordered_set<int> uset(nums.begin(), nums.end());
                for (auto &num : uset) {// Traverse uset to avoid too many duplicate elements when traversing nums
                        if (!uset.count(num - 1)) { // The smallest one in the consecutive sequence
                                curr = 1;
                                while (uset.count(num + curr)) {
                                        curr++;
                                }
                                longest = std::max(longest, curr);
                        }
                }
                return longest;
        }
};

You can also find the largest one in a sequence:

#include <vector>
#include <unordered_set>
#include <algorithm>
using std::vector;
using std::unordered_set;

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

                int n = nums.size();
                int cnt, max_val = 0;                

                // First find the end of the sequence
                for (int curr : uset) {
                        if (uset.count(curr + 1) != 0)
                                continue;
                        
                        // curr is now the last element of a consecutive sequence
                        cnt = 1;
                        while (uset.count(curr - cnt) != 0)
                                cnt++;
                        max_val = std::max(max_val, cnt);
                }
                return max_val;
        }
};