Longest Consecutive Sequence in Python

Longest Consecutive Sequence

Are you looking for a way to solve the Longest Consecutive Sequence in Python? This problem is a common challenge in coding interviews, where you need to find the length of the longest consecutive elements sequence in an array. It tests your skills in array manipulation, set operations in Python, and algorithm design. Using Python's powerful features like sets and loops, you can solve this efficiently with an O(n) time complexity. Curious to learn how to solve the longest sequence problem in Python and apply these techniques? Let’s solve!

Steps to Solve Longest Consecutive Sequence

• Understand the Problem:
  • The task is to find the length of the longest sequence of consecutive numbers in an unsorted array.
• Use a Set for Fast Lookups:
  • Convert the array to a Python set to enable O(1) time complexity for checking the existence of numbers.
• Iterate Through the Array:
  • For each number in the set, check if it is the start of a sequence by verifying that (num - 1) is not in the set.
• Count the Length of the Sequence:
  • For numbers that are the start of a sequence, keep incrementing the count while (num + 1) exists in the set.
• Track the Maximum Length:
  • Keep a variable to store the length of the longest sequence encountered during the iteration.
• Handle Edge Cases:
  • If the array is empty, return 0.
  • For arrays with a single number, the longest sequence length is 1.
• Test the Solution:
  • Example input: [100, 4, 200, 1, 3, 2]
  • Output: 4 (sequence: [1, 2, 3, 4]).

Problem statement

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

Example

1
2
nums = [100, 4, 200, 1, 3, 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def longestConsecutive(nums):
    if not nums:
        return 0

    num_set = set(nums)
    longest_streak = 0

    for num in nums:
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            longest_streak = max(longest_streak, current_streak)

    return longest_streak

# Example usage
nums1 = [100, 4, 200, 1, 3, 2]
nums2 = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]

print("Longest consecutive sequence length:", longestConsecutive(nums1))  # Output: 4
print("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!