[Python/C++] O(n) Clear Explanation Illustrated with Example
Intuition\nIn the array, there could be multiple groups of consecutive numbers. Ideally, we want to process each group only once to achieve the O(n) time comple
**Intuition**\nIn the array, there could be multiple groups of consecutive numbers. Ideally, we want to process each group only once to achieve the O(n) time complexity specified in the problem statement. To do this, let\'s count the size of each group only when we are at the smallest element in the group. To check that the current number `num` is the first element in a group, it is sufficient to check that `num - 1` doesn\'t appear in `nums`.\n\n**Example**\nSuppose `nums = [100,2,101,3,1]`. There are 2 groups of consecutive numbers in `nums`, namely `[1,2,3]` and `[100,101]`.  We iterate through `nums`:\n1. `[100,2,101,3,1]`\n`__^____________`\nSince `100-1=99` is in `nums`, we count the group size that `100` is part of by incrementing `100` until it is no longer in the set. After incrementing from `100 -> 101`, we stop, since `102` is not in `nums`. So we now know `100` is the start of a group of size 2.\n\n2. `[100,2,101,3,1]`\n`_____^_________`\n`2` is not the start of a group, since `2-1=1` is in `nums`, so we skip to the next element.\n\n3. `[100,2,101,3,1]`\n`________^______`\nWe skip `101` since `101-1=100` is in `nums`.\n\n4. `[100,2,101,3,1]`\n`___________^___`\nWe skip `3` since `3-1=2` is in `nums`.\n\n5. `[100,2,101,3,1]`\n`_____________^_`\nWe know `1` is that first number in a group since `1-1=0` is not in `nums`. We keep incrementing `1` until it is no longer contained in `nums`.  After incrementing from `1 -> 2 -> 3` we stop, since the next number `4` is not contained in `nums`. Thus, we know `1` is the start of a group of size `3`.\n\n**Python**\n```python\nclass Solution:\n    def longestConsecutive(self, nums: List[int]) -> int:\n        num_set = set(nums)\n        \n        longest_sequence = 0\n        for num in nums:\n            if num - 1 in num_set:\n                continue\n            current_length = 1\n            while num + 1 in num_set:\n                num += 1\n                current_length += 1\n            longest_sequence = max(longest_sequence, current_length)\n        return longest_sequence\n```\n\n**C++**\n```c++\nclass Solution {\npublic:\n    int longestConsecutive(vector<int>& nums) {\n        unordered_set<int> nums_set(nums.begin(), nums.end());\n        \n        int longest_sequence = 0;\n        for (int num : nums) {\n            if (nums_set.count(num - 1)) continue;\n            int current_length = 1;\n            while (nums_set.count(num + 1)) {\n                num++;\n                current_length++;\n            }\n            longest_sequence = max(longest_sequence, current_length);\n        }\n        return longest_sequence;\n    }\n};\n```\n\n**Time Complexity**: O(n) - On the surface, it looks like the time complexity might be O(n^2) because of the `while` loop nested inside the `for` loop. But actually, each element in `nums` is processed at most twice. We only run the `while` loop when we\'re at the start of a group, otherwise we skip to the next element.\n \n**Space Complexity**: O(n) - We\'re creating a set which contains each element in `nums`.\n\n**Upvote** if you found this explanation and example helpful!\n\n**Join our discord** to meet other people prepping for interviews!\n**https://discord.gg/7wpQQFYC**
['C', 'Python', 'C++']