Longest Consecutive Sequence - Leetcode Solution

The Longest Consecutive Sequence problem on LeetCode can be solved using the concept of hashing. The problem statement is as follows.

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,

Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

To solve this problem, we can follow the below steps.

1. Create a hash set and add all the elements of the input array to the set.

2. Initialize a variable maxLength to store the length of the longest consecutive sequence found so far.

3. Iterate through the input array and for each element i, we will check if i - 1 is present in the hash set. If it is present, then it means that i is not the start of a sequence, so we can skip this iteration and move on to the next element.

4. If i - 1 is not present in the hash set, then it means that i is the start of a sequence. So we will iterate through the hash set and find the length of the consecutive sequence starting from i. We will update maxLength if the length of this sequence is greater than maxLength.

5. After iterating through all the elements in the input array, we will return maxLength.

The Python code for the solution is as follows.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        maxLength = 0
        
        for num in nums:
            if num - 1 not in numSet:
                currLength = 1
                while num + 1 in numSet:
                    currLength += 1
                    num += 1
                maxLength = max(maxLength, currLength)
        
        return maxLength

Time Complexity: O(n), where n is the length of the input array.

Space Complexity: O(n), where n is the length of the input array, since we are using a hash set to store all the elements of the input array.

1