Interview Classic 150 Questions P128 Longest Consecutive Sequence

---

Timeline

Timeline

2025-11-14

init

Hash table

---

Problem:

P128 Longest Consecutive Sequence

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

Use a hash set. Although there is a while loop inside a for loop, overall each element is visited only once. The core idea is to find the minimum of each consecutive sequence each time, then find the subsequent consecutive elements of that sequence. Note that when traversing, iterate over the uset to avoid too many duplicate elements when iterating over 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) {// Iterate over uset to avoid too many duplicate elements when iterating over 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;
        }
};