Longest Consecutive Sequence in Python

The longest consecutive sequence problem involves finding the length of the longest sequence of consecutive integers in an unsorted array. This problem is commonly encountered in technical interviews and tests your ability to efficiently manipulate arrays and sets to find the solution.

Problem statement

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

Example

1nums = [100, 4, 200, 1, 3, 2]
2# Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4], which has a length of 4.

How to solve

To solve the Longest Consecutive Sequence problem efficiently, we can use a hash set to keep track of the numbers. This allows for O(1) average time complexity for both checking the existence of a number and inserting a new number. The idea is to iterate through the array and, for each number, check if it is the start of a sequence (i.e., there is no number num-1 in the set). If it is, then we count the length of the sequence starting from that number.

Full code in Python

Here's the complete Python code to solve the Longest Consecutive Sequence problem:

1def longestConsecutive(nums):
2    if not nums:
3        return 0
4
5    num_set = set(nums)
6    longest_streak = 0
7
8    for num in nums:
9        if num - 1 not in num_set:
10            current_num = num
11            current_streak = 1
12
13            while current_num + 1 in num_set:
14                current_num += 1
15                current_streak += 1
16
17            longest_streak = max(longest_streak, current_streak)
18
19    return longest_streak
20
21# Example usage
22nums1 = [100, 4, 200, 1, 3, 2]
23nums2 = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
24
25print("Longest consecutive sequence length:", longestConsecutive(nums1))  # Output: 4
26print("Longest consecutive sequence length:", longestConsecutive(nums2))  # Output: 9

Explanation of the code

• Convert Array to Set: Convert the input array nums to a set num_set to allow O(1) time complexity for lookups.
• Initialize Longest Streak: Initialize longest_streak to 0 to keep track of the longest sequence length found.
• Check for Start of Sequence: Iterate through the array, and for each number, check if it is the start of a sequence by verifying that num - 1 is not in num_set.
• Count Sequence Length: If the number is the start of a sequence, count the length of the sequence by incrementing current_num and current_streak as long as current_num + 1 is in the set.
• Update Longest Streak: Update longest_streak with the maximum length found during the iteration.
• Return Result: Return longest_streak as the length of the longest consecutive sequence.

Time complexity

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because each element is processed once during the iteration.

Conclusion

In conclusion, the Longest Consecutive Sequence problem in Python can be efficiently solved using a hash set to ensure optimal time and space complexity. Understanding this approach helps improve your problem-solving skills for similar challenges. Happy coding!