✅ [C++/Python] Simple Solution w/ Explanation | O(n³) -> O(n)
Given an unsorted array of integers nums, we need to return the length of the longest consecutive elements sequence.\ne.g.:\n\ntext\nnums = [0, 3, 2, 1, 5, 6, 9
Given an *unsorted* array of integers `nums`, we need to return the length of the longest consecutive elements sequence.\ne.g.:\n\n```text\nnums = [0, 3, 2, 1, 5, 6, 9]\n\nConsecutive Elements of length\n1: [0], [1], [2], [3], [5], [6], [9]\n2: [5, 6]\n4: [0, 1, 2, 3]\n\nHence, we return 4\n```\n\nIt is explicitly mentioned in the problem statement that the algorithm should be of time complexity `O(n)`, so sorting the array is out of the question.\n\nI then thought of a solution that is `O(n)` which is as follows:\n\n1. Use a boolean array, where the index represents the number itself to store if the number is present or not.\n2. Then traverse through this array to find the longest consecutive `True` values.\n\ne.g.:\n\n```text\nnums = [0, 3, 2, 1, 5, 6, 9]\nbool_arr = [True, True, True, True, False, True, True, False, False, True]\n              |     |     |     |     |      |     |     |      |      |\n              0     1     2     3     4      5     6     7      8      9\n\nThe largest consecutive sequence with True values is of length 4, which is our answer.\n```\n\nI then looked at the constraints, which mention `-10\u2079 <= nums[i] <= 10\u2079`, so this approach also cannot be used as both time and space complexity would be of order ~`2*10\u2079`, which is high.\n\nSo, let\'s think of a brute-force approach and then optimize it.\n___\n___\n\u274C **Solution I: Brute-force [TLE]**\n\nStarting from each `num` in the `nums` array, we try to build a consecutive sequence and check if it is the longest. We can do this by checking if `num + 1` is present or not; if present, then check if `num + 2` is present or not and so on.\n\n<iframe src="https://leetcode.com/playground/R7vj6zuS/shared" frameBorder="0" width="1080" height="330"></iframe>\n\n- **Time Complexity:** `O(n\xB3)`\n    > The outer `for` loop runs `n` times. The inner `while` loop can run upto `n` times for the worst case if the entire array forms consecutive sequence, and finding `curr_num + 1 in nums` has complexity `0(n)`.\n- **Space Complexity:** `O(1)`\n\n___\n\u274C **Solution II: Optimized Brute-force + HashSet [TLE]**\n\nWe are checking if `curr_num + 1` is present in the array in `O(n)` time. We can optimize this lookup to `O(1)` using a HashSet.\n\n<iframe src="https://leetcode.com/playground/HWrbwqqR/shared" frameBorder="0" width="1080" height="340"></iframe>\n\n- **Time Complexity:** `O(n\xB2)`\n    > We reduced the lookup to `O(1)` and everything else remains the same.\n- **Space Complexity:** `O(n)`\n\n___\n\u2705 **Solution III: Super Optimized Brute-force + HashSet [Accepted]**\n\nWe are still doing many repetitive works. This can be understood by the following example:\n\n```text\nnums = [1, 2, 3, 4, 5]\n1. num = 1\n   a. curr_num = 1, curr_len = 1, while condition: True\n   b. curr_num = 2, curr_len = 2, while condition: True\n   c. curr_num = 3, curr_len = 3, while condition: True\n   d. curr_num = 4, curr_len = 4, while condition: True\n   e. curr_num = 5, curr_len = 5, while condition: False\n\n2. num = 2\n    a. curr_num = 2, curr_len = 1, while condition: True\n    b. curr_num = 3, curr_len = 2, while condition: True\n    c. curr_num = 4, curr_len = 3, while condition: True\n    d. curr_num = 5, curr_len = 4, while condition: False\n.\n.\n.\n```\n\nThis redundancy can be removed in multiple ways. One way could be to use an extra HashSet to store the information that the number is already a part of a sequence that was processed earlier. So, in the previous example, no need to run the inner `while` loop as `2` was already processed. Furthermore, the inner `while` loop won\'t run for `num = 3, 4 and 5`.\nThere is one more interesting way. Considering the previous example, after `num = 1` has been processed, `num` becomes `2`. Now we can check if `1,` i.e. `num - 1` is present in the array or not. If present, there is no need to run the inner `while` loop, as it was processed earlier or will be processed later. What do I mean by "will be processed later"? This will become clear in the following example.\n\n```text\nnums = [2, 3, 1, 4, 5]\n1. num = 2\n   1 is present -> Don\'t run the inner loop\n2. num = 3\n   2 is present -> Don\'t run the inner loop\n3. curr_num = 1\n   0 is not present -> Run the inner loop\n   a. curr_num = 1, curr_len = 1, while condition: True\n   b. curr_num = 2, curr_len = 2, while condition: True\n   c. curr_num = 3, curr_len = 3, while condition: True\n   d. curr_num = 4, curr_len = 4, while condition: True\n   e. curr_num = 5, curr_len = 5, while condition: False\n```\n\n<iframe src="https://leetcode.com/playground/Ps5QMtvx/shared" frameBorder="0" width="1080" height="380"></iframe>\n\nIn short, the inner while loop will only start if any `num` in `nums` is the start of a new consecutive sequence.\n\n- **Time Complexity:** `O(n)`\n    > This is actually tricky. One may think there are two nested loops, and the complexity should be `O(n\xB2)`. But, this is not the case. To understand this, focus on my statement just after the code. The `while` loop will only execute when `num` is the start of a sequence and will run up to `n` times for the worst case. So, let\'s say `nums = [3, 5, 1, 2, 7, 6]`. The `while` loop will only execute when `num = 1 or 5`, which will run till `3` and `7`, respectively. So, the array is covered only once!\n- **Space Complexity:** `O(n)`\n\n___\n**Update:**\nThe code can be made even faster if we run the `for` loop through the set instead of the original array. This is because we are not considering duplicate elements. Thanks to [@dennisthomas2002](https://leetcode.com/dennisthomas2002/) and [@shivangtomar](https://leetcode.com/shivangtomar/) for their suggestions.\n\n```python\nclass Solution:\n    def longestConsecutive(self, nums: List[int]) -> int:\n        max_len = 0\n        num_set = set(nums)\n        for num in num_set:\n            if num - 1 not in num_set:\n                curr_num = num\n                curr_len = 1\n                while curr_num + 1 in num_set:\n                    curr_num += 1\n                    curr_len += 1\n                max_len = max(max_len, curr_len)\n        return max_len\n```\n\nThis solution was inspired by [@StefanPochmann](https://leetcode.com/StefanPochmann/)\'s solution [here](https://leetcode.com/problems/longest-consecutive-sequence/discuss/41057/Simple-O(n)-with-Explanation-Just-walk-each-streak).\n___\n___\nIf you like the solution, please **upvote**! \uD83D\uDD3C\nFor any questions, or discussions, comment below. \uD83D\uDC47\uFE0F\n
['C', 'Python']