128_longest_consecutive_sequence.cc

#include <unordered_map>
#include <vector>
 
// Time: O(N), Space: O(N)
// While the solution is asymptotically optimal, the implementation is absurd
 
class Solution {
public:
    int longestConsecutive(std::vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
 
        std::unordered_map<int, bool> htable;
        for (const int& n: nums) htable[n] = false;
 
        // determine starts of sequences
        int answer = 1;
 
        for (auto& [key, val]: htable) {
            if (htable.contains(key - 1)) continue;
 
            int seqLen = 1, curr = key;
            //        obvious|-------------------|will be checked only for last element in seq
            while (htable.contains(curr + 1) || htable.contains(curr - 1)) {
                // std::cout << "Incrementing for curr = " << curr << "\n";
                curr++;
                if (!htable.contains(curr)) break;
                seqLen++;
            }
 
            if (seqLen > answer) answer = seqLen;
        }
 
        return answer;
    }
};