Longest Consecutive Sequence | JS, Python, Java, C++ | Easy O(N) Map Solution w/ Explanation
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nIn 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**.\n\n_(**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)**.)_\n\nIf 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.\n\n_(**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**.)_\n\nBut 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.\n\n_(**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.)_\n\nThen, 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.\n\nFor 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**).\n\nThen, 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**).\n\nThen 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**).\n\nAt 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**.\n\n - _**Time Complexity: O(N)** where **N** is the length of **nums**_\n - _**Space Complexity: O(N)** for **nmap** and **seen**_\n\n---\n\n#### ***Javascript Code:***\n```javascript\nvar longestConsecutive = function(nums) {\n    let nmap = new Map(), ans = 0,\n        seen = new Uint32Array(nums.length)\n    for (let i = 0; i < nums.length; i++)\n        if (!nmap.has(nums[i])) nmap.set(nums[i], i)\n    for (let n of nums) {\n        let curr = n, count = 1\n        if (seen[nmap.get(curr)]) continue\n        while (nmap.has(curr+1)) {\n            let ix = nmap.get(++curr)\n            if (seen[ix]) {\n                count += seen[ix]\n                break\n            } else seen[ix] = 1, count++\n        }\n        seen[nmap.get(n)] = count\n        ans = Math.max(ans, count)\n    }\n    return ans\n};\n```\n\n---\n\n#### ***Python Code:***\n```python\nclass Solution:\n    def longestConsecutive(self, nums: List[int]) -> int:\n        nmap, seen, ans = defaultdict(int), [0] * len(nums), 0\n        for i in range(len(nums)):\n            if nums[i] not in nmap: nmap[nums[i]] = i\n        for n in nums:\n            curr, count = n, 1\n            if seen[nmap[n]]: continue\n            while curr+1 in nmap:\n                curr += 1\n                ix = nmap[curr]\n                if seen[ix]:\n                    count += seen[ix]\n                    break\n                else:\n                    seen[ix] = 1\n                    count += 1\n            seen[nmap[n]], ans = count, max(ans, count)\n        return ans\n```\n\n---\n\n#### ***Java Code:***\n```java\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        Map<Integer, Integer> nmap = new HashMap<>();\n        int ans = 0;\n        int[] seen = new int[nums.length];\n        for (int i = 0; i < nums.length; i++)\n            if (!nmap.containsKey(nums[i])) nmap.put(nums[i], i);\n        for (int n : nums) {\n            int curr = n, count = 1;\n            if (seen[nmap.get(curr)] > 0) continue;\n            while (nmap.containsKey(curr+1)) {\n                int ix = nmap.get(++curr);\n                if (seen[ix] > 0) {\n                    count += seen[ix];\n                    break;\n                } else {\n                    seen[ix] = 1;\n                    count++;\n                }\n            }\n            seen[nmap.get(n)] = count;\n            ans = Math.max(ans, count);\n        }\n        return ans;\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n```c++\nclass Solution {\npublic:\n    int longestConsecutive(vector<int>& nums) {\n        unordered_map<int, int> nmap;\n        int ans = 0;\n        vector<int> seen(nums.size());\n        for (int i = 0; i < nums.size(); i++)\n            if (nmap.find(nums[i]) == nmap.end())\n                nmap[nums[i]] = i;\n        for (auto& n : nums) {\n            int curr = n, count = 1;\n            if (seen[nmap[curr]]) continue;\n            while (nmap.find(curr+1) != nmap.end()) {\n                int ix = nmap[++curr];\n                if (seen[ix]) {\n                    count += seen[ix];\n                    break;\n                } else seen[ix] = 1, count++;\n            }\n            seen[nmap[n]] = count;\n            ans = max(ans, count);\n        }\n        return ans;\n    }\n};\n```
[]