Jobs

Interviews

Discussions

Longest Consecutive Sequence

Medium

Apple

2 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^5
-10^9 <= nums[i] <= 10^9

Longest Consecutive Sequence

Medium

Apple

2 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^5
-10^9 <= nums[i] <= 10^9

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 values for the integers in the input array?
Can the input array `nums` be empty or null?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?
If there are multiple longest consecutive sequences of the same length, should I return the length of any one of them?
Is the input array guaranteed to contain only integers, or could there be other data types?

Brute Force Solution

Approach

The brute force approach to finding the longest consecutive sequence in a list of numbers involves checking all possible sequences within the list. We consider each number as the potential start of a consecutive sequence and then try to build the sequence from there.

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

For every number in the list, imagine it's the beginning of a possible consecutive sequence.
Starting with that number, check if the next number in the sequence (one larger than the current number) is also in the list.
If the next number is present, add it to your sequence and check for the number after that (again, one larger).
Keep extending the sequence as long as you find consecutive numbers in the list.
Once you can no longer extend the sequence, record the length of the sequence you found.
Repeat this process for every number in the original list, always trying to build the longest sequence possible from that starting point.
After checking all numbers and finding all possible consecutive sequences, identify the sequence with the greatest length. That's your longest consecutive sequence.

Code Implementation

def longest_consecutive_sequence_brute_force(numbers):
    longest_streak = 0

    for number in numbers:
        current_number = number
        current_streak = 1

        # Try to find the next numbers in the sequence
        while True:
            next_number = current_number + 1

            if next_number in numbers:

                # Increase the sequence length
                current_streak += 1
                current_number = next_number
            else:
                break

        # Update the longest streak
        if current_streak > longest_streak:
            longest_streak = current_streak

    return longest_streak

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each of the n numbers in the input array. For each number, the inner loop attempts to extend a consecutive sequence by repeatedly searching for the next number in the sequence within the input array. In the worst case, for each of the n starting numbers, we might need to scan almost the entire array to determine if the next consecutive element exists. Therefore, the time complexity becomes proportional to n * n, which simplifies to O(n²).

Space Complexity

O(1) – The provided brute force approach iterates through the input list of numbers and checks for consecutive numbers. It doesn't use any auxiliary data structures like temporary lists, hash maps, or sets to store intermediate results or track visited numbers. The space used remains constant regardless of the input list size (N) as it only uses a few variables to track sequence lengths during the comparisons, so the space complexity is O(1).

Optimal Solution

Approach

The core idea is to efficiently build the longest possible chain of consecutive numbers. We'll use a tool to quickly check if a number is present and only start building chains from numbers that are the beginning of a sequence.

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

First, put all the numbers into a special tool that lets you quickly check if a number exists.
Then, go through each number. If the number before it is also present, skip it – it is not the beginning of a sequence.
If the number is indeed the beginning of a sequence, start counting how long that sequence is by repeatedly checking if the next number exists.
Keep track of the longest sequence you find. Return the length of the longest sequence.

Code Implementation

def longestConsecutive(nums):
    number_set = set(nums)

    longest_streak = 0

    for number in nums:
        # Check if this is the start of a sequence
        if (number - 1) in number_set:
            continue

        current_number = number
        current_streak = 1

        # Count how long the sequence is
        while (current_number + 1) in number_set:
            current_number += 1
            current_streak += 1

        # Update the longest streak found so far
        longest_streak = max(longest_streak, current_streak)

    return longest_streak

Big(O) Analysis

Time Complexity

O(n) – The algorithm first populates a set with n elements, which takes O(n) time. Then, it iterates through the input array of size n. Inside the loop, there is a while loop that extends the consecutive sequence as long as the next number is present in the set. Since each number in the input array is checked at most once during the sequence extension (because once a number is part of a counted sequence, its preceding number will be skipped), the while loop's cumulative execution across all iterations of the outer loop is bounded by O(n). Thus, the overall time complexity is O(n + n), which simplifies to O(n).

Space Complexity

O(N) – The primary contributor to the space complexity is the 'special tool' mentioned in the explanation, which is used to quickly check the existence of a number. This is most efficiently implemented using a hash set or a similar data structure. In the worst-case scenario, the hash set will store all N numbers from the input array. Therefore, the auxiliary space used grows linearly with the input size N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there's no sequence.
Array with one element	Return 1, as a single element constitutes a sequence of length 1.
Array with all identical numbers	The longest sequence length is 1 since elements must be strictly increasing.
Array with consecutive numbers in reverse order	The solution should correctly identify the sequence when numbers are not pre-sorted.
Array with duplicate numbers and some valid sequence	The solution must only count each number once in a sequence using a set to track visited elements.
Array with negative and positive numbers forming a sequence	The solution should handle both positive and negative numbers correctly.
Large input array with a very long consecutive sequence	The solution should use an efficient data structure like a set to ensure O(n) time complexity.
Integer overflow if sequence contains very large numbers	Use appropriate data types and consider checking for potential overflow if necessary, though this is usually not directly relevant to the main algorithmic logic.

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 values for the integers in the input array?
Can the input array `nums` be empty or null?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?
If there are multiple longest consecutive sequences of the same length, should I return the length of any one of them?
Is the input array guaranteed to contain only integers, or could there be other data types?

Brute Force Solution

Approach

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

For every number in the list, imagine it's the beginning of a possible consecutive sequence.
Starting with that number, check if the next number in the sequence (one larger than the current number) is also in the list.
If the next number is present, add it to your sequence and check for the number after that (again, one larger).
Keep extending the sequence as long as you find consecutive numbers in the list.
Once you can no longer extend the sequence, record the length of the sequence you found.
Repeat this process for every number in the original list, always trying to build the longest sequence possible from that starting point.
After checking all numbers and finding all possible consecutive sequences, identify the sequence with the greatest length. That's your longest consecutive sequence.

Code Implementation

def longest_consecutive_sequence_brute_force(numbers):
    longest_streak = 0

    for number in numbers:
        current_number = number
        current_streak = 1

        # Try to find the next numbers in the sequence
        while True:
            next_number = current_number + 1

            if next_number in numbers:

                # Increase the sequence length
                current_streak += 1
                current_number = next_number
            else:
                break

        # Update the longest streak
        if current_streak > longest_streak:
            longest_streak = current_streak

    return longest_streak

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, put all the numbers into a special tool that lets you quickly check if a number exists.
Then, go through each number. If the number before it is also present, skip it – it is not the beginning of a sequence.
If the number is indeed the beginning of a sequence, start counting how long that sequence is by repeatedly checking if the next number exists.
Keep track of the longest sequence you find. Return the length of the longest sequence.

Code Implementation

def longestConsecutive(nums):
    number_set = set(nums)

    longest_streak = 0

    for number in nums:
        # Check if this is the start of a sequence
        if (number - 1) in number_set:
            continue

        current_number = number
        current_streak = 1

        # Count how long the sequence is
        while (current_number + 1) in number_set:
            current_number += 1
            current_streak += 1

        # Update the longest streak found so far
        longest_streak = max(longest_streak, current_streak)

    return longest_streak

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there's no sequence.
Array with one element	Return 1, as a single element constitutes a sequence of length 1.
Array with all identical numbers	The longest sequence length is 1 since elements must be strictly increasing.
Array with consecutive numbers in reverse order	The solution should correctly identify the sequence when numbers are not pre-sorted.
Array with duplicate numbers and some valid sequence	The solution must only count each number once in a sequence using a set to track visited elements.
Array with negative and positive numbers forming a sequence	The solution should handle both positive and negative numbers correctly.
Large input array with a very long consecutive sequence	The solution should use an efficient data structure like a set to ensure O(n) time complexity.
Integer overflow if sequence contains very large numbers	Use appropriate data types and consider checking for potential overflow if necessary, though this is usually not directly relevant to the main algorithmic logic.