# 128. Longest Consecutive Sequence 🔍

**Difficulty**: `Medium` - **Tags**: `Array`, `Hash Table`, `Union Find`

[LeetCode Problem Link](https://leetcode.com/problems/longest-consecutive-sequence/)

***

## Problem Statement 📜

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.

***

## Examples 🌟

🔹 **Example 1:**

**Input:**

```plaintext
nums = [100, 4, 200, 1, 3, 2]
```

**Output:**

```plaintext
4
```

**Explanation:** The longest consecutive elements sequence is `[1, 2, 3, 4]`. Therefore, its length is `4`.

🔹 **Example 2:**

**Input:**

```plaintext
nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
```

**Output:**

```plaintext
9
```

***

## Constraints ⚙️

* `0 <= nums.length <= 10^5`
* `-10^9 <= nums[i] <= 10^9`

***

## Solution 💡

To achieve an `O(n)` time complexity, a `HashSet` can be used to store all elements of the array. This allows us to quickly check the existence of consecutive elements.

***

### Java Solution (Using HashSet)

```java
import java.util.HashSet;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        HashSet<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int longestStreak = 0;

        for (int num : numSet) {
            // Only start a sequence if num is the beginning of the sequence
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}
```

***

## Explanation of the Solution

1. **Use HashSet for Fast Lookup**:
   * Insert all elements into a `HashSet` for `O(1)` average-time checks.
2. **Start from Sequence Beginning**:
   * Iterate through the `HashSet`.
   * Start counting the streak only if the current number is the start of a sequence (`num - 1` is not in the set).
3. **Count Consecutive Numbers**:
   * Increment the count while consecutive numbers exist.
4. **Track the Longest Streak**:
   * Update the longest streak as needed.

***

## Time Complexity ⏳

* **O(n)**: Each element is processed at most twice.

## Space Complexity 💾

* **O(n)**: Space required for the `HashSet`.

You can find the full solution [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%205%20Hashmap/047%20Longest%20Consecutive%20Sequence/Solution.java).


---

# 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://chunhthanhde.gitbook.io/leetcode-top-interview/topic-5-hashmap/047-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.