Split Array into Consecutive Subsequences

Medium

Amazon

1 view

Topics:

ArraysGreedy Algorithms

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
All subsequences have a length of 3 or more.

Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

Example 1:

Input: nums = [1,2,3,3,4,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

Example 2:

Input: nums = [1,2,3,3,4,4,5,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

Example 3:

Input: nums = [1,2,3,4,4,5]
Output: false
Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

Constraints:

1 <= nums.length <= 10⁴
-1000 <= nums[i] <= 1000
nums is sorted in non-decreasing order.

Split Array into Consecutive Subsequences

Medium

Amazon

1 view

Topics:

ArraysGreedy Algorithms

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
All subsequences have a length of 3 or more.

Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

Example 1:

Input: nums = [1,2,3,3,4,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

Example 2:

Input: nums = [1,2,3,3,4,4,5,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

Example 3:

Input: nums = [1,2,3,4,4,5]
Output: false
Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

Constraints:

1 <= nums.length <= 10⁴
-1000 <= nums[i] <= 1000
nums is sorted in non-decreasing order.

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 expected behavior if the input array cannot be split into consecutive subsequences as described?
Can the input array contain negative numbers?
Are duplicate numbers allowed in the input array, and if so, how should they be handled when forming consecutive subsequences?
What is the minimum length required for a valid consecutive subsequence?
Is the input array guaranteed to be sorted, or do I need to handle unsorted input?

Brute Force Solution

Approach

The brute force method involves checking absolutely every possible way to split the given set of numbers. We explore all combinations, ensuring each resulting sequence meets the 'consecutive' and 'at least 3 elements' requirements. This approach guarantees finding a solution, if one exists, by sheer exhaustive testing.

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

Try starting the first consecutive sequence with the first number.
See if the next numbers are consecutive and extend the sequence.
Check if the sequence has at least three numbers. If not, it's no good.
If it does, remove this first sequence from the original set of numbers.
Now, try to split the remaining numbers into another valid consecutive sequence following the same rules.
Keep repeating this process to split the remaining numbers into consecutive sequences until there are no numbers left.
If at any point you can't form a valid sequence, go back and try a different way of forming the previous sequences.
Repeat this entire process, starting the initial sequence with the second number, then the third, and so on to cover all possible starting points.
After exploring all possibilities, determine if at least one combination successfully splits the entire set of numbers into valid consecutive sequences.

Code Implementation

def split_array_into_consecutive_subsequences(numbers):
    def can_split(remaining_numbers, sequences):
        if not remaining_numbers:
            return True

        first_number = remaining_numbers[0]
        
        for sequence_length in range(3, len(remaining_numbers) + 1):
            potential_sequence = [first_number + i for i in range(sequence_length)]

            # Check if a potential consecutive sequence exists
            if all(number in remaining_numbers for number in potential_sequence):
                
                new_remaining_numbers = list(remaining_numbers)
                for number in potential_sequence:
                    new_remaining_numbers.remove(number)

                # Recursively check if the rest can be split
                if can_split(new_remaining_numbers, sequences + [potential_sequence]):
                    return True

        return False

    # Try every starting point to create the sequences
    for start_index in range(len(numbers)): 
        if can_split(numbers, []):
            return True

    # Return false if no split is found
    return False

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach explores all possible ways to split the input array of size n into consecutive subsequences. In the worst-case scenario, it might need to check all permutations of subsequence splits to find a valid combination. Checking all permutations typically grows factorially with the input size. Therefore, the time complexity is proportional to n!, representing the number of possible arrangements to consider. Finding all the combinations in a problem like this will lead to exponential growth, especially when dealing with checking sub-sequences.

Space Complexity

O(N) – The brute force approach described necessitates creating a modified copy of the input array to represent the remaining numbers after extracting a consecutive subsequence. In the worst-case scenario, where the first subsequence extracted is very short, multiple copies of nearly the entire input array of size N may be created and stored simultaneously due to recursion. Therefore, the auxiliary space required grows linearly with the size of the input array. This leads to an auxiliary space complexity of O(N).

Optimal Solution

Approach

The trick is to efficiently track how many unfinished sequences we have waiting for the next number. We use this information to greedily extend sequences whenever possible, creating new sequences only when absolutely necessary.

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

Count how many times each number appears in the input.
Go through the numbers one by one, in the order they appear.
If a number exists, first check if it can extend an existing sequence.
If it can extend a sequence, continue that sequence, and reduce the count of that number.
If the number cannot extend a sequence, try to start a brand new sequence with the current number and the next two numbers.
If the current number is not part of an existing sequence, and cannot start a new sequence (because the next two numbers do not exist) then we know we can not split the sequence.
If all numbers have been processed and no illegal sequences were detected, the split is valid.

Code Implementation

def is_possible_to_split(nums): 
    number_counts = {} 
    for number in nums: 
        number_counts[number] = number_counts.get(number, 0) + 1 

    tails = {} 

    for number in nums: 
        if number_counts[number] == 0: 
            continue

        if tails.get(number - 1, 0) > 0: 
            # Extend an existing sequence.
            tails[number - 1] -= 1 
            tails[number] = tails.get(number, 0) + 1 
            number_counts[number] -= 1 

        elif number_counts.get(number, 0) > 0 and \
             number_counts.get(number + 1, 0) > 0 and \
             number_counts.get(number + 2, 0) > 0: 
            # Start a new sequence.
            number_counts[number] -= 1 
            number_counts[number + 1] -= 1 
            number_counts[number + 2] -= 1 

            tails[number + 2] = tails.get(number + 2, 0) + 1 

        else: 
            # Cannot extend or start a sequence.
            return False 

    return True

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input array of size n once to count the frequency of each number. Then, we iterate through the numbers again, at most once per number, to either extend existing sequences or start new ones. Each of these operations (decrementing counts, checking for extensions, starting sequences) takes constant time. Therefore, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a frequency count to store the number of times each number appears in the input. This frequency count requires a data structure, such as a hash map or an array, that can store a count for each unique number in the input. In the worst case, all N numbers in the input are unique, resulting in a space complexity proportional to N for the frequency count. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return False since no subsequences can be formed.
Input array with fewer than 3 elements	Return False because a consecutive subsequence must have length at least 3.
Input array with all the same numbers (e.g., [1, 1, 1, 1])	Return False as it's impossible to create consecutive subsequences of length at least 3.
Negative numbers in the input array	The frequency map correctly handles negative numbers and their counts.
Presence of zero in the input array	The logic will properly check for consecutive sequences including zero.
Array is sorted but no consecutive sequence of length 3 or more exists	The algorithm should return False in this scenario after iterating through the array.
The input array is very large, causing potential memory issues if storing all numbers	Use an iterative approach with constant space instead of recursion to avoid stack overflow.
Integer overflow when checking for consecutive values	Ensure that data types used for calculations (e.g., next value checks) can accommodate potentially large numbers.