0128. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence

Description

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

ac1: priority queue

class Solution {
    public int longestConsecutive(int[] nums) {
        // edge cases
        if (nums.length < 2) return nums.length;

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        for (int i : nums) {
            pq.offer(i);
        }

        int max = 1;
        int len = 1;
        int prev = pq.poll();
        while (!pq.isEmpty()) {
            int n = pq.poll();
            if (n == prev + 1) {
                len++;
                max = Math.max(max, len);
            } else if (n > prev + 1) {
                len = 1;
            }
            prev = n;
        }

        return max;
    }
}
// priority queue

ac2: set

class Solution {
    public int longestConsecutive(int[] nums) {
        // edge cases
        if (nums == null || nums.length == 0) return 0;

        Set<Integer> set = new HashSet<>();
        for (int i : nums) set.add(i);

        int lgst = 0;
        for (int n : set) {
            if (set.contains(n - 1)) continue; // 100, 4, 200, 1, 3, 2. if meet 3, skip, cause we will start from 1

            int cnt = 0;
            while (set.contains(n)) {
                cnt++;
                n++;
            }

            lgst = Math.max(lgst, cnt);
        }

        return lgst;
    }
}

/*
sort, nlogn
set, O(n)
map, O(n)
*/

ac3: map

https://leetcode.com/problems/longest-consecutive-sequence/discuss/41055/My-really-simple-Java-O(n)-solution-Accepted

public int longestConsecutive(int[] num) {
    int res = 0;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int n : num) {
        if (!map.containsKey(n)) {
            int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
            int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
            // sum: length of the sequence n is in
            int sum = left + right + 1;
            map.put(n, sum);

            // keep track of the max length 
            res = Math.max(res, sum);

            // extend the length to the boundary(s)
            // of the sequence
            // will do nothing if n has no neighbors
            map.put(n - left, sum);
            map.put(n + right, sum);
        }
        else {
            // duplicates
            continue;
        }
    }
    return res;
}

ac4: union find

https://leetcode.com/problems/longest-consecutive-sequence/discuss/41062/My-Java-Solution-using-UnionFound/39220

class Union_Find{
public:
    Union_Find (int N) {
        for (int i = 0; i < N; i++) {
            id.push_back(i);
            sz.push_back(1);
        }
    }

    void Union(int A, int B) {
        int rootA = Find(A);
        int rootB = Find(B);
        if (rootA == rootB) return;
        if (sz[rootA] < sz[rootB]) {
            id[rootA] = rootB;
            sz[rootB] += sz[rootA];
        } else {
            id[rootB] = rootA;
            sz[rootA] += sz[rootB];
        }
    }

    int Find(int p) {
        while (p != id[p]) {
            id[p] = id[id[p]];
            p = id[p];
        }
        return p;
    }

    int maxSize() {
        int res = 0;
        for (auto s : sz)
            res = max(res, s);
        return res;
    }

private:
    vector<int> id;
    vector<int> sz;
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        Union_Find uf(nums.size());
        unordered_map<int, int> mapIndex;
        for (int i = 0; i < nums.size(); i++) {
            if (mapIndex.count(nums[i])) continue; // in case of duplicate
            mapIndex.insert(make_pair(nums[i], i));

            if (mapIndex.count(nums[i] + 1)) {
                uf.Union(i, mapIndex[nums[i] + 1]);
            }
            if (mapIndex.count(nums[i] - 1)) {
                uf.Union(i, mapIndex[nums[i] - 1]);
            }
        }
        return uf.maxSize();
    }
};