longestsubseq.cpp

#include <iostream>
using namespace std;

const int HASH_SIZE = 200003; // A large prime number
const int EMPTY = 2000000001; // Sentinel value for empty slot

class HashSet {
    int* table;

public:
    HashSet() {
        table = new int[HASH_SIZE];
        for (int i = 0; i < HASH_SIZE; i++) {
            table[i] = EMPTY;
        }
    }

    int hash(int key) {
        long long h = (1LL * key % HASH_SIZE + HASH_SIZE) % HASH_SIZE;
        return (int)h;
    }

    void insert(int key) {
        int h = hash(key);
        while (table[h] != EMPTY && table[h] != key) {
            h = (h + 1) % HASH_SIZE;
        }
        table[h] = key;
    }

    bool contains(int key) {
        int h = hash(key);
        int start = h;
        while (table[h] != EMPTY) {
            if (table[h] == key) return true;
            h = (h + 1) % HASH_SIZE;
            if (h == start) break;
        }
        return false;
    }

    ~HashSet() {
        delete[] table;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;

        HashSet set;
        for (int i = 0; i < n; i++) {
            set.insert(nums[i]);
        }

        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int streak = 1;

                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    streak++;
                }

                if (streak > maxLen) {
                    maxLen = streak;
                }
            }
        }

        return maxLen;
    }
};