Longest Consecutive Sequence FAANG Python Interview Question

Given an array of integers , return the length of the longest consecutive sequence of elements that can be formed from the array.

A consecutive sequence consists of elements where each element is exactly greater than the previous element. The elements in the sequence can be selected from any position in the array and do not need to appear in their original order.

Example #1

Input:

Output:

Explanation: The longest consecutive is which have a length of

Example #2

Input:

Output:

Explanation: The longest consecutive is which have a length of

This isn't a HARD problem, but it's one that has multiple solutions. Your interviewer might have you solve it one way and then ask you to propose other options while comparing their strengths and weaknesses.

Let's explore three different ways to solve this problem and compare them.

Brute Force Approach

In interviews, it's always a good idea to start with the brute force approach and build upon it. That's also what the interviewer expects from you.

For our case, what if we start from each number in the list and keep going while the numbers are consecutive? The main question is: how can we tell if the numbers are consecutive?

One way is to check if the current number plus exists in the array. If it does, that means we can keep going. We update the current number and keep checking for the next one.

Implementation

For fast lookup, we'll use a set, since checking if an element exists in a set takes $O(1)$ time.

Here's is the summary of what we are gonna do:

1. Convert the list to a set for fast lookup.
2. Iterate over each number in the list.
3. Start a new consecutive sequence at each number.
4. Keep incrementing the number while it exists in the set.
5. Update the global maximum length when the sequence ends.

Here's the code to do that:

Time Complexity Analysis

This solution has $O(n²)$ time complexity because we start a new sequence from every number. For example, if we have numbers from to , the algorithm starts a new sequence at each of them, making the time complexity $O(n × (n - 1))$ ≈ $O(n²)$.

Improved Brute Force Approach

The previous solution has two inefficiencies:

1. Unnecessary iterations: If there are duplicate numbers, we start a sequence for each of them, even though we only need to start once.
2. Starting from the wrong position: If a number is part of an existing larger sequence, there's no need to start a new sequence from it. For example, in , the longest sequence starts at . If we start at or , we won’t find a longer sequence.

Optimizations

1. Use a set to avoid duplicate numbers.
2. Only start a sequence if the number is the smallest in its sequence. That is, only start when is not in the set.

Here's the code to do that:

Time Complexity Analysis

In the worst case, we iterate at most twice over the set (once for iterating, once for counting sequences), making the time complexity $O(n)$.

Sorting Approach

Another way to solve this problem is by sorting the list. If we sort it, all consecutive numbers will be placed next to each other. Then, we can iterate through the sorted list and count the length of each consecutive sequence. The longest such sequence will be our answer.

Implementation

1. Sorting the array: Since consecutive numbers will be next to each other in a sorted list, this makes it easier to detect sequences.
2. Iterate through the sorted array: We start from the first element and attempt to find the longest consecutive sequence.
3. Handling duplicates: If the difference between the current number and the previous one is , we simply skip it because it doesn't contribute to the sequence length.
4. Detecting a break in the sequence: If the difference between the current number and the previous one is , we continue the sequence and increment the size counter. However, if the difference is more than , we stop the sequence and update the maximum length if needed.
5. Move to the next sequence: Instead of checking all numbers one by one, we jump directly to the index where the sequence was last counted.

Here's the corrected and optimized code:

Time Complexity Analysis

• Sorting takes $O(n \log n)$.
• Iterating through the sorted list takes $O(n)$.
  Overall time complexity is $(O(n \log n))$, which is worse than the $O(n)$ solution using sets but still much better than the brute force $O(n^2)$.