# 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

```java
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

```java
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](https://leetcode.com/problems/longest-consecutive-sequence/discuss/41055/My-really-simple-Java-O%28n%29-solution-Accepted)

```java
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>

```java
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();
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0128-longest-consecutive-sequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.