Longest Consecutive Sequence 🎯

Welcome to another engaging tutorial on CodeYourCraft! Today, we're diving into the fascinating world of data structures and algorithms, focusing on the Longest Consecutive Sequence problem. By the end of this lesson, you'll not only understand the concept but also learn to solve it with code. Let's get started! 📝

Understanding the Problem

In the Longest Consecutive Sequence problem, given an unsorted array of integers, find the length of the longest consecutive sequence.

For example, consider the array:

[100, 4, 200, 1, 3, 200, 1200]

The longest consecutive sequence is [4, 200, 1, 3, 200], which has a length of 5.

Breaking it Down

To solve this problem, we'll approach it in three steps:

Identify all the unique numbers in the array.
Sort them in ascending order.
Find the longest consecutive sequence.

Identifying Unique Numbers

First, let's write a function to identify all unique numbers in the array:

python

def find_unique(numbers):
    unique_numbers = set()
    for number in numbers:
        unique_numbers.add(number)
    return unique_numbers

💡 Pro Tip: Using a set data structure in Python helps to remove duplicates as it only stores unique elements.

Sorting the Numbers

Next, let's sort the unique numbers in ascending order:

python

def sort_unique(unique_numbers):
    return sorted(list(unique_numbers))

Finding the Longest Consecutive Sequence

Finally, we'll write a function to find the longest consecutive sequence using the sorted unique numbers:

python

def find_longest_sequence(unique_numbers):
    longest_sequence = [unique_numbers[0]]
    current_sequence = [unique_numbers[0]]

    for number in unique_numbers:
        if number - 1 == current_sequence[-1]:
            current_sequence.append(number)
        elif number > current_sequence[-1] + 1:
            current_sequence = [number]
        if len(current_sequence) > len(longest_sequence):
            longest_sequence = current_sequence

    return longest_sequence

📝 Note: This function works by iterating through the sorted unique numbers. If the current number is consecutive to the last number in the current sequence, it adds the current number to the sequence. If the current number is more than one greater than the last number in the sequence, it starts a new sequence. The function keeps track of the longest sequence found so far.

Putting it All Together

Now, let's create a function to solve the Longest Consecutive Sequence problem with an unsorted array:

python

def longest_consecutive(numbers):
    unique_numbers = find_unique(numbers)
    sorted_numbers = sort_unique(unique_numbers)
    longest_sequence = find_longest_sequence(sorted_numbers)

    return len(longest_sequence)

Testing our Solution

Let's test our solution on the given example:

python

numbers = [100, 4, 200, 1, 3, 200, 1200]
length = longest_consecutive(numbers)
print(f"The length of the longest consecutive sequence is: {length}")

You should see the output: The length of the longest consecutive sequence is: 5

Challenge 🌟

Write a function to find the longest consecutive sequence in the following array: [13, 6, 1, 10, 15, 3, 21, 26, 8, 20, 19, 12, 7].

:::quiz Question: Write a function to find the longest consecutive sequence in the following array: [13, 6, 1, 10, 15, 3, 21, 26, 8, 20, 19, 12, 7].

python

def longest_consecutive(numbers):
    unique_numbers = find_unique(numbers)
    sorted_numbers = sort_unique(unique_numbers)
    longest_sequence = find_longest_sequence(sorted_numbers)

    return len(longest_sequence)

numbers = [13, 6, 1, 10, 15, 3, 21, 26, 8, 20, 19, 12, 7]
length = longest_consecutive(numbers)
print(f"The length of the longest consecutive sequence is: {length}")

Correct: ✅

Explanation: This function solves the Longest Consecutive Sequence problem by identifying unique numbers, sorting them, and finding the longest sequence using the functions we've previously defined. The output for the given array is The length of the longest consecutive sequence is: 6.