✅ Longest Consecutive Sequence | Short & Easy Solution w/ Explanation | Hashset
\u2714\uFE0F Solution - I (Sorting)\n\nWe can simply sort the given array and compare consecutive elements. Following cases exists:\n1. nums[i] == nums[i-1] + 1
\u2714\uFE0F ***Solution - I (Sorting)***\n\nWe can simply sort the given array and compare consecutive elements. Following cases exists:\n1. **`nums[i] == nums[i-1] + 1`**: This means the current element is consecutive to previous, so increment current streak count.\n2. **`nums[i] == nums[i-1]`**: We have found the same element as previous. Skip it, and see if we can still extend the sequence with next elements.\n3. **None of above** : We can\'t extend the sequence any further. Update *`longest`* to store longest formed streak till now and reset *`curlongest`*.\n\n**C++**\n```\nint longestConsecutive(vector<int>& nums) {\n\tif(!size(nums)) return 0;\n\tsort(begin(nums), end(nums));\n\tint longest = 0, cur_longest = 1;\n\tfor(int i = 1; i < size(nums); i++) \n\t\tif(nums[i] == nums[i - 1]) continue;\n\t\telse if(nums[i] == nums[i - 1] + 1) cur_longest++; // consecutive element - update current streak length\n\t\telse longest = max(longest, cur_longest), cur_longest = 1;  // reset current streak length\n\treturn max(longest, cur_longest);\n}\n```\n\n---\n\n**Python**\n```\ndef longestConsecutive(self, nums: List[int]) -> int:\n\tnums.sort()\n\tlongest, cur_longest = 0, min(1, len(nums))\n\tfor i in range(1,len(nums)):\n\t\tif nums[i] == nums[i - 1] : continue\n\t\tif nums[i] == nums[i - 1] + 1: cur_longest += 1\n\t\telse: longest, cur_longest = max(longest, cur_longest), 1\n\treturn max(longest, cur_longest)\n```\n\n***Time Complexity :*** **`O(NlogN)`**, where *`N`* is the number of elements in nums\n***Time Complexity :*** **`O(1)`**, ignoring the space required by sorting algorithm.\n\n---\n\n\u2714\uFE0F ***Solution - II (Using Hashset)***\n\nWe need to find the longest consecutive sequence in linear time. We can do this if we insert all the elements of *`nums`* into a hashset. Once we have inserted all the elements, we can just iterate over the hashset to find longest consecutive sequence involving  the current element(let\'s call it *`num`*) under iteration. This can simply be done by **iterating over elements that are consecutive to *`num`* till we keep finding them in the set**. Each time we will also delete those elements from set to ensure we only visit them once.\n\n**C++**\n```\nint longestConsecutive(vector<int>& nums) {\n\tunordered_set<int> s(begin(nums), end(nums)); // inserting all elements into hashset\n\tint longest = 0;\n\tfor(auto& num : s) {\n\t\tint cur_longest = 1;\n\t\t// find consecutive elements in the backward and forward direction from num\n\t\tfor(int j = 1; s.count(num - j); j++) s.erase(num - j), cur_longest++;\n\t\tfor(int j = 1; s.count(num + j); j++) s.erase(num + j), cur_longest++;\n\t\tlongest = max(longest, cur_longest);  // update longest to hold longest consecutive sequence till now\n\t}\n\treturn longest;\n}\n```\n\n---\n\n**Python**\n```\ndef longestConsecutive(self, nums: List[int]) -> int:\n\tlongest, s = 0, set(nums)\n\tfor num in nums:\n\t\tcur_longest, j = 1, 1\n\t\twhile num - j in s: \n\t\t\ts.remove(num - j)\n\t\t\tcur_longest, j = cur_longest + 1, j + 1\n\t\tj = 1\n\t\twhile num + j in s: \n\t\t\ts.remove(num + j)\n\t\t\tcur_longest, j = cur_longest + 1, j + 1\n\t\tlongest = max(longest, cur_longest)\n\treturn longest\n```\n\n***Time Complexity :*** **`O(N)`**\n***Space Complexity :*** **`O(N)`**\n\n---\n\n\u2714\uFE0F ***Solution - III (Using Hashset - w/ optimizations)***\n\nWe can form a solution without the need to spend time erasing elements from the hashset. \n\nInstead of taking the first element that we find in the hashset and iterating both forward and backward, we can just keep skipping till we find that hashset contains `num - 1`. Finally, we can just iterate in the forward direction till we find consecutive elements in hashset and update `longest` at the end\n\n**C++**\n```\nint longestConsecutive(vector<int>& nums) {\n\tunordered_set<int> s(begin(nums), end(nums));\n\tint longest = 0;\n\tfor(auto& num : s) {\n        if(s.count(num - 1)) continue;\n\t\tint j = 1;\n\t\twhile(s.count(num + j)) j++;\n\t\tlongest = max(longest, j);\n\t}\n\treturn longest;\n}\n```\n\n---\n\n**Python**\n```\ndef longestConsecutive(self, nums):\n\ts, longest = set(nums), 0\n\tfor num in s:\n\t\tif num - 1 in s: continue\n\t\tj = 1\n\t\twhile num + j in s: j += 1\n\t\tlongest = max(longest, j)\n\treturn longest\n```\n\n***Time Complexity :*** **`O(N)`**\n***Space Complexity :*** **`O(N)`**\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
['C']