128: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nSolution: We can use a hash set to store all the elements in the input ar
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nSolution: We can use a hash set to store all the elements in the input array. We can then traverse the input array and for each element check if the element is the start of the sequence. If the element is the start of the sequence, we can keep incrementing the element by 1 and checking if the next element is present in the hash set. We keep incrementing the element until we reach the end of the sequence, and update the length of the longest sequence found so far.\n\nAlgorithm:\n\n1. Create an empty hash set.\n2. Add all elements of the input array to the hash set.\n3. Initialize a variable to store the length of the longest sequence found so far to 0.\n4. For each element in the input array, do the following:\na. If the element is the start of the sequence (i.e., the element-1 is not present in the hash set), do the following:\ni. Initialize a variable to store the length of the current sequence to 1.\nii. Keep incrementing the element by 1 and checking if the next element is present in the hash set.\niii. If the next element is present in the hash set, increment the length of the current sequence by 1.\niv. If the length of the current sequence is greater than the length of the longest sequence found so far, update the length of the longest sequence found so far.\n5. Return the length of the longest sequence found so far.\n# Complexity\n- Time complexity:\nTime Complexity: O(n) - We traverse the input array once and perform constant time operations for each element.\n- Space complexity:\nSpace Complexity: O(n) - We create a hash set to store all the elements in the input array.\n\n# Code\n```\nclass Solution:\n    def longestConsecutive(self, nums: List[int]) -> int:\n        num_set = set(nums)\n        longest_seq = 0\n        \n        for num in num_set:\n            if num-1 not in num_set:\n                current_num = num\n                current_seq = 1\n                while current_num+1 in num_set:\n                    current_num += 1\n                    current_seq += 1\n                longest_seq = max(longest_seq, current_seq)\n                \n        return longest_seq\n\n```
['Array', 'Hash Table', 'Union Find', 'Python', 'Python3']