Jobs

Interviews

Discussions

Longest Consecutive Sequence

Medium

Google

47 views

Topics:

Arrays

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

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Example 3:

Input: nums = [1,0,1,2]
Output: 3

Constraints:

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Longest Consecutive Sequence

Medium

Google

47 views

Topics:

Arrays

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

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Example 3:

Input: nums = [1,0,1,2]
Output: 3

Constraints:

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values in the input array? Can I assume there is a reasonable upper and lower bound?
Are there any duplicate numbers in the input array, and if so, how should they be handled?
What should be returned if the input array is empty or null?
If there are multiple longest consecutive sequences of the same length, is it sufficient to return the length of any one of them?
Can you provide a few example inputs and expected outputs for clarification?

Brute Force Solution

Approach

The brute force strategy for finding the longest consecutive sequence involves checking every number in the input to see how long a sequence it can start. We consider each number as a potential beginning of a sequence and explore as far as we can.

Here's how the algorithm would work step-by-step:

Pick a number from the given set.
See if the next number in the sequence exists in the set. For example, if you picked 5, check if 6 is present.
If the next number exists, check for the number after that, and so on. For example, if 6 exists, check if 7 exists.
Keep counting how many consecutive numbers you find, forming a sequence, from the initially picked number.
Repeat this process, starting with a different number from the set each time.
Keep track of the longest sequence you've found so far.
Once you've checked every number in the set, the longest sequence you've tracked is the answer.

Code Implementation

def longest_consecutive_sequence_brute_force(numbers):
    longest_streak = 0

    for number in numbers:
        current_number = number
        current_streak = 1

        # Iterate while the next number is in the set
        while True:
            next_number = current_number + 1
            if next_number in numbers:

                #If the next number exists, extend current streak
                current_streak += 1
                current_number = next_number
            else:
                break

        # Update longest streak if needed
        longest_streak = max(longest_streak, current_streak)

    return longest_streak

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through each of the n elements in the input array, considering each as the potential start of a consecutive sequence. For each such element, it repeatedly checks for the presence of the next consecutive number in the set, potentially scanning through the array multiple times. In the worst case, for each of the n elements, we might need to check up to n elements to determine the length of the sequence. Therefore, the overall time complexity is proportional to n * n, which simplifies to O(n²).

Space Complexity

O(1) – The provided brute force strategy does not use any auxiliary data structures. It only iterates through the input set and uses a few variables to keep track of the current number, the next number to check, and the length of the current consecutive sequence. Therefore, the space required is constant and does not depend on the size of the input set, N.

Optimal Solution

Approach

The goal is to find the longest string of numbers in a given set where each number follows the next in order (like 1, 2, 3). The trick is to avoid doing unnecessary work by focusing only on the starting points of these sequences. We use a set to efficiently check if a number could be the start of such a sequence.

Here's how the algorithm would work step-by-step:

First, put all the given numbers into a collection like a bag where you can quickly check if a number exists.
Next, for each number, check if the number right before it is in our 'bag'. If it is, this number isn't the start of a sequence, so we skip it.
If the number is potentially the start of a sequence, we then try to build the entire sequence from it. We repeatedly check if the next number in the sequence exists in our 'bag'.
As we build the sequence, we keep track of how long it is.
Finally, we remember the longest sequence we found and return that length. This way, we only try to build sequences from their potential starting points, avoiding extra work.

Code Implementation

def longest_consecutive_sequence(numbers):
    number_set = set(numbers)
    longest_sequence_length = 0

    for number in numbers:

        # Skip if 'number' is part of a longer sequence already.
        if (number - 1) in number_set:
            continue

        current_number = number
        current_sequence_length = 1

        # Build the sequence as long as the next number exists.
        while (current_number + 1) in number_set:
            current_number += 1
            current_sequence_length += 1

        # Update the longest sequence found so far.
        longest_sequence_length = max(longest_sequence_length, current_sequence_length)

    return longest_sequence_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The initial step of adding all numbers to a set takes O(n) time. The main loop iterates through each of the n numbers in the input. Inside the loop, the 'if' condition checks for the existence of the previous number in the set, which is O(1). The 'while' loop, which extends the consecutive sequence, on average, will not run for every number. This is because it only runs when a number is the potential start of a sequence. Each number within the input can only be part of one consecutive sequence. Therefore, the total number of times the 'while' loop iterates across all numbers remains bounded by n. Therefore, the overall time complexity approximates O(n).

Space Complexity

O(N) – The solution uses a set to store all the numbers from the input array. This set requires space proportional to the number of elements in the input, where N is the number of integers in the input array. Therefore, the auxiliary space used is directly dependent on the size of the input. No other significant auxiliary space is used beyond this set, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 since there are no elements to form a consecutive sequence.
Input array with only one element	Return 1 as a single element is a consecutive sequence of length one.
Input array with all identical elements	Return 1 as the longest consecutive sequence is of length one (e.g., [2,2,2] should return 1).
Input array with consecutive elements at the beginning and end, that when connected, form a longer sequence	The algorithm must correctly identify and merge overlapping sequences, like [1,2,3,7,8,9].
Input array with negative numbers	The algorithm should handle negative numbers correctly, and the presence of negative numbers should not affect the O(n) time complexity.
Large input array with a wide range of integers (potential integer overflow)	Use a data structure like a hash set to avoid sorting and prevent integer overflow during comparisons.
Input array with duplicates	Use a set to remove duplicate numbers and ensure each number is only considered once during sequence building.
Maximum-sized input array with extremely long consecutive sequence.	Verify that the data structure used to store the numbers (e.g., hash set) can handle a large number of elements without excessive memory consumption or performance degradation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values in the input array? Can I assume there is a reasonable upper and lower bound?
Are there any duplicate numbers in the input array, and if so, how should they be handled?
What should be returned if the input array is empty or null?
If there are multiple longest consecutive sequences of the same length, is it sufficient to return the length of any one of them?
Can you provide a few example inputs and expected outputs for clarification?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Pick a number from the given set.
See if the next number in the sequence exists in the set. For example, if you picked 5, check if 6 is present.
If the next number exists, check for the number after that, and so on. For example, if 6 exists, check if 7 exists.
Keep counting how many consecutive numbers you find, forming a sequence, from the initially picked number.
Repeat this process, starting with a different number from the set each time.
Keep track of the longest sequence you've found so far.
Once you've checked every number in the set, the longest sequence you've tracked is the answer.

Code Implementation

def longest_consecutive_sequence_brute_force(numbers):
    longest_streak = 0

    for number in numbers:
        current_number = number
        current_streak = 1

        # Iterate while the next number is in the set
        while True:
            next_number = current_number + 1
            if next_number in numbers:

                #If the next number exists, extend current streak
                current_streak += 1
                current_number = next_number
            else:
                break

        # Update longest streak if needed
        longest_streak = max(longest_streak, current_streak)

    return longest_streak

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, put all the given numbers into a collection like a bag where you can quickly check if a number exists.
Next, for each number, check if the number right before it is in our 'bag'. If it is, this number isn't the start of a sequence, so we skip it.
If the number is potentially the start of a sequence, we then try to build the entire sequence from it. We repeatedly check if the next number in the sequence exists in our 'bag'.
As we build the sequence, we keep track of how long it is.
Finally, we remember the longest sequence we found and return that length. This way, we only try to build sequences from their potential starting points, avoiding extra work.

Code Implementation

def longest_consecutive_sequence(numbers):
    number_set = set(numbers)
    longest_sequence_length = 0

    for number in numbers:

        # Skip if 'number' is part of a longer sequence already.
        if (number - 1) in number_set:
            continue

        current_number = number
        current_sequence_length = 1

        # Build the sequence as long as the next number exists.
        while (current_number + 1) in number_set:
            current_number += 1
            current_sequence_length += 1

        # Update the longest sequence found so far.
        longest_sequence_length = max(longest_sequence_length, current_sequence_length)

    return longest_sequence_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 since there are no elements to form a consecutive sequence.
Input array with only one element	Return 1 as a single element is a consecutive sequence of length one.
Input array with all identical elements	Return 1 as the longest consecutive sequence is of length one (e.g., [2,2,2] should return 1).
Input array with consecutive elements at the beginning and end, that when connected, form a longer sequence	The algorithm must correctly identify and merge overlapping sequences, like [1,2,3,7,8,9].
Input array with negative numbers	The algorithm should handle negative numbers correctly, and the presence of negative numbers should not affect the O(n) time complexity.
Large input array with a wide range of integers (potential integer overflow)	Use a data structure like a hash set to avoid sorting and prevent integer overflow during comparisons.
Input array with duplicates	Use a set to remove duplicate numbers and ensure each number is only considered once during sequence building.
Maximum-sized input array with extremely long consecutive sequence.	Verify that the data structure used to store the numbers (e.g., hash set) can handle a large number of elements without excessive memory consumption or performance degradation.