Solution: Longest Consecutive Sequence
Tags: algorithms, javascript, java, python
Published: 2021-06-06 20:41:41

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/longest-consecutive-sequence/discuss/1254716).*

---

#### [Leetcode Problem #128 (*Medium*): Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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:| 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 <= 10^5
 - -10^9 <= nums[i] <= 10^9

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

In order to accomplish this task in **O(N) time**, we'll have to have some way of looking up values (**nmap**), which means a **set** or **map** object. We'll also need some way of keeping track of which numbers have already been **seen**.

_(**Note**: We could forego the **seen** data structure entirely and just follow each path to its end every time, but that would cause us to redo the same sections over and over again, pushing the **time complexity** to **O(N^2)**.)_

If we use a set for **nmap**, then we would need to use a map for **seen** in order to be able to look the numbers up by value. If we instead use a map for **nmap**, with each number pointing to its index, then we can instead use those indexes with an **array** for **seen**, which will be more efficient.

_(**Note**: Since we'll be iterating through **nums** from front to back in the next section, we should make sure that we store only the first index at which a number is found in **nmap**. Later indexes of duplicate numbers can be ignored, as by then the number will already be considered **seen**.)_

But now we run into the issue of potentially finding the middle of a sequence before we find the beginning of the sequence. For this we can take inspiration from a **union-find** approach and/or **dynamic programming** (**DP**) approach; We can use **seen** to store the length of the sequence found when starting at the given number.

_(**Note**: We don't need to store path length data in any but the smallest number of a found chain, as those nodes can never be actively visited again. Only the entry point, which is the smallest number, needs to have the accurate path length stored. For the other numbers, we just have to register them as seen, so we can just fill them with a **1** or any **non-zero** number to make the check easy.)_

Then, if we later find an earlier number in the same sequence, we can notice the value stored in **seen** when we link up with an already-visited tail end of the same sequence and just add that value (representing the tail's length) to our **count** of numbers.

For example, consider **nums = [4,5,6,1,2,3,0]**. We start at **4**, then track through **5** and **6**, filling the **seen** indexes corresponding to **5** and **6** with a **1** each (**seen[1] = 1**, **seen[2] = 1**). Once we reach the end of that chain and have a **count** of **3**, we store that **3** in the **seen** index corresponding to **4** (**seen[0] = 3**).

Then, because we've seen **5** and **6** while checking **4**, we skip to **1**. At **1**, we track through **2** and **3**, filling them with **1**s (**seen[4] = 1**, **seen[5] = 1**). After that, we run into **4**, which has a value of **3** stored in **seen**. At this point, **count** is **3** (from numbers **1**, **2**, and **3**), but we've just run into another already-discovered chain of **3** (numbers **4**, **5**, and **6**), so we can fill the **seen** index corresponding to **1** with a **6** (**seen[3] = 6**).

Then we skip past **2** and **3**, and the **0** will lead us back to **1**, so we'll have a result of **7** for the **seen** index corresponding to **0** (**seen[6] = 7**).

At each step, when we're about to store the **count** in **seen**, we can also update our best result so far (**ans**). Then, once we've reached the end of the iteration, we can just **return ans**.

 - _**Time Complexity: O(N)** where **N** is the length of **nums**_
 - _**Space Complexity: O(N)** for **nmap** and **seen**_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var longestConsecutive = function(nums) {
    let nmap = new Map(), ans = 0,
        seen = new Uint32Array(nums.length)
    for (let i = 0; i < nums.length; i++)
        if (!nmap.has(nums[i])) nmap.set(nums[i], i)
    for (let n of nums) {
        let curr = n, count = 1
        if (seen[nmap.get(curr)]) continue
        while (nmap.has(curr+1)) {
            let ix = nmap.get(++curr)
            if (seen[ix]) {
                count += seen[ix]
                break
            } else seen[ix] = 1, count++
        }
        seen[nmap.get(n)] = count
        ans = Math.max(ans, count)
    }
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nmap, seen, ans = defaultdict(int), [0] * len(nums), 0
        for i in range(len(nums)):
            if nums[i] not in nmap: nmap[nums[i]] = i
        for n in nums:
            curr, count = n, 1
            if seen[nmap[n]]: continue
            while curr+1 in nmap:
                curr += 1
                ix = nmap[curr]
                if seen[ix]:
                    count += seen[ix]
                    break
                else:
                    seen[ix] = 1
                    count += 1
            seen[nmap[n]], ans = count, max(ans, count)
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> nmap = new HashMap<>();
        int ans = 0;
        int[] seen = new int[nums.length];
        for (int i = 0; i < nums.length; i++)
            if (!nmap.containsKey(nums[i])) nmap.put(nums[i], i);
        for (int n : nums) {
            int curr = n, count = 1;
            if (seen[nmap.get(curr)] > 0) continue;
            while (nmap.containsKey(curr+1)) {
                int ix = nmap.get(++curr);
                if (seen[ix] > 0) {
                    count += seen[ix];
                    break;
                } else {
                    seen[ix] = 1;
                    count++;
                }
            }
            seen[nmap.get(n)] = count;
            ans = Math.max(ans, count);
        }
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> nmap;
        int ans = 0;
        vector<int> seen(nums.size());
        for (int i = 0; i < nums.size(); i++)
            if (nmap.find(nums[i]) == nmap.end())
                nmap[nums[i]] = i;
        for (auto& n : nums) {
            int curr = n, count = 1;
            if (seen[nmap[curr]]) continue;
            while (nmap.find(curr+1) != nmap.end()) {
                int ix = nmap[++curr];
                if (seen[ix]) {
                    count += seen[ix];
                    break;
                } else seen[ix] = 1, count++;
            }
            seen[nmap[n]] = count;
            ans = max(ans, count);
        }
        return ans;
    }
};
```