# x 128. Longest Consecutive Sequence

[128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/)\\

### With range

> time: O(n)

> space: O(n)

```java
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    const set = new Set(nums);

    const ranges = {};

    let max = 0;
    for (const x of set) {
        const left = ranges[x - 1] ?? 0;
        const right = ranges[x + 1] ?? 0;
        const dis = right + left + 1;

        ranges[x] = dis;
        max = Math.max(max, dis);

        // TODO why?
        ranges[x - left] = dis;
        ranges[x + right] = dis;
    }

    return max;
};
```

> 4 6 3 2 8 1 5

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | - | - | - | - | - | - | - | - | - |
|   | 6 | 3 | 2 | 4 | 6 | 6 |   | 1 |   |
|   |   |   |   |   |   |   |   |   |   |

### With Set

> time: O(n)

> Space: O(n)

```java
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    const set = new Set(nums);

    let max = 0;
    for (let i = 0; i < nums.length; i++) {
        const curr = nums[i];

        if (set.size === 0) break;

        if (!set.has(curr)) {
            continue;
        }

        let left = curr - 1;
        let right = curr + 1;
        while (set.delete(left)) {
            left--;
        }
        while (set.delete(right)) {
            right++;
        }

        max = Math.max(max, right - left - 1);

    }

    return max;
};
```

### solutions

<https://leetcode.com/problems/longest-consecutive-sequence/solutions/41055/my-really-simple-java-o-n-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;
}
```

```java
public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for(int i : nums) set.add(i);
        int ans = 0;
        for(int num : nums) {
            int left = num - 1;
            int right = num + 1;
            while(set.remove(left)) left--;
            while(set.remove(right)) right++;
            ans = Math.max(ans,right - left - 1);
            if(set.isEmpty()) return ans;//save time if there are items in nums, but no item in hashset.
        }
        return ans;
    }
```


---

# 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://algorithm.prettylog.com/top-75-leetcode-questions-to-save-your-time/problems/graph/x-128.-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.