Longest Consecutive Sequence LeetCode 128 [Python Solution]

The Longest Consecutive Sequence LeetCode problem is a classic, often asked by top tech companies during interviews, including Google.

The task is to find the length of the longest consecutive sequence in an unsorted array of integers.

For example, given an input array like [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4], with a length of 4.

It’s essential to note that the order of the numbers in the input array doesn’t matter; we’re interested in finding the longest consecutive sequence within the array.

A straightforward approach to solving this problem is to sort the array, which would give us the desired sequence.

However, this approach has a time complexity of O(n log n), which may not be efficient for large datasets. The challenge is to come up with a more efficient solution that runs in O(n) time.

Longest Consecutive Sequence LeetCode Constraints

Before diving into the solution, let’s first understand the constraints of this problem:

The length of the input array nums can range from 0 to 10^5.
The integers in the array can have values between -10^9 and 10^9.

Efficient Solution

Now, let’s explore a more efficient solution. To tackle this problem, we can visualize the numbers on an imaginary number line. This visualization helps us recognize distinct sequences.

We notice that each sequence has a starting value with no left neighbor. For instance, in the array [100, 4, 200, 1, 3, 2], the starting values for the sequences are 100, 4, and 1. These starting values have no left neighbors.

We can efficiently determine the start of each sequence by converting our initial array nums into a set. Then, we iterate through the array and check if a number has a left neighbor by verifying if n - 1 exists in the set. If it doesn’t have a left neighbor, it’s the start of a sequence.

Once we identify the start of a sequence, we can count how many consecutive numbers come after it. We do this by checking if n + 1 exists in the set.

If it does, we continue to extend the sequence. This process continues until there’s no longer a consecutive number.

By iterating through the entire array and using a set to check the existence of neighbors, we can efficiently find the length of each sequence.

Since we visit each number at most twice, the solution runs in O(n) time. Additionally, we only use one data structure, which is the set, keeping our memory complexity at O(n).

Longest Consecutive Sequence Solution in Python

Now, let’s dive into the Python code that implements this efficient solution:

View on GitHub ➹

def longestConsecutive(self, nums: List[int]) -> int:
    num_set = set(nums)
    longest = 0

    for num in num_set:
        if (num - 1) not in num_set:  # Check if it's the start of a sequence
            length = 1
            while (num + length) in num_set:  # Continue to extend the sequence
                length += 1
            longest = max(length, longest)

    return longest

This concise code efficiently finds the length of the longest consecutive sequence in the given array.

Time and Space Complexity

The time complexity of this solution is O(n) because we iterate through the entire array and visit each number at most twice.

The space complexity is also O(n) because we use a set to store the elements of the input array.

Next Questions To Tackle

Conclusion

The Longest Consecutive Sequence problem, often asked in coding interviews, can be solved efficiently in Python with an O(n) time complexity.

By visualizing the problem on an imaginary number line and using a set to identify the start of sequences, we can find the longest consecutive sequence in an unsorted array.

This solution offers a more efficient alternative to sorting the array, making it suitable for large datasets.

If you have any questions, suggestions, or comments, feel free to share them. Happy coding!

Question Link

Remember, understanding these problem-solving techniques and algorithms is essential for excelling in coding interviews and real-world programming scenarios.