Jobs

Interviews

Discussions

Ways to Split Array Into Three Subarrays

Medium

Google

5 views

Topics:

ArraysBinary Search

A split of an integer array is good if:

The array is split into three non-empty contiguous subarrays - named left, mid, right respectively from left to right.
The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 10⁹+ 7.

Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].

Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

Constraints:

3 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁴

Ways to Split Array Into Three Subarrays

Medium

Google

5 views

Topics:

ArraysBinary Search

A split of an integer array is good if:

The array is split into three non-empty contiguous subarrays - named left, mid, right respectively from left to right.
The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 10⁹+ 7.

Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].

Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

Constraints:

3 <= nums.length <= 10⁵
0 <= 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 are the possible value ranges for the elements in the input array?
Can the input array be empty or contain only one or two elements? If so, what should I return?
What defines a valid split? Specifically, is it acceptable for the sums of two subarrays to be equal, or must they be strictly increasing? (sum1 < sum2 < sum3)
If multiple valid splits are possible, should I return a count of all such splits, or return a single example split?
Does the array contain only integers?

Brute Force Solution

Approach

The problem asks us to divide a series of numbers into three continuous groups. The brute force method involves checking every possible way to make those divisions, one by one, to see if they meet a certain condition.

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

First, consider all possible places to make the first split in the series of numbers.
For each of those first splits, consider all possible places to make the second split. This creates your three groups.
For each set of three groups you've now created, check if the sum of the numbers in the first group is less than or equal to the sum of the numbers in the second group, and if the sum of the numbers in the second group is less than or equal to the sum of the numbers in the third group.
If both conditions are true for a particular set of three groups, we have found a valid way to split the series.
Continue checking all possible split locations until all combinations have been examined.
Keep a running total of all the valid ways you find to split the series.
The final total represents the answer.

Code Implementation

def ways_to_split_array_brute_force(numbers):
    total_ways = 0
    array_length = len(numbers)

    for first_split_index in range(array_length - 2):

        for second_split_index in range(first_split_index + 1, array_length - 1):
            # Calculate sums of the three subarrays
            first_subarray_sum = sum(numbers[:first_split_index + 1])

            second_subarray_sum = sum(numbers[first_split_index + 1:second_split_index + 1])

            third_subarray_sum = sum(numbers[second_split_index + 1:])

            # Check if the sums meet the condition
            if (first_subarray_sum <= second_subarray_sum and
                    second_subarray_sum <= third_subarray_sum):
                # Increment the count if valid
                total_ways += 1

    return total_ways

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through all possible first split positions, which takes O(n) time. For each first split, it then iterates through all possible second split positions to create three subarrays, also taking O(n) time in the worst case. Calculating the sums of the three subarrays takes constant time O(1) for each split configuration. Therefore, the overall time complexity is dominated by the nested loops, resulting in approximately n * n operations, which simplifies to O(n^2).

Space Complexity

O(1) – The provided plain English explanation outlines a brute-force approach. The algorithm iterates through possible split locations without creating auxiliary data structures like lists or hash maps to store intermediate results or visited combinations. It keeps track of the split locations using a few integer variables. Therefore, the auxiliary space required remains constant, independent of the input array's size (N). The space complexity is O(1).

Optimal Solution

Approach

The goal is to divide a collection of numbers into three groups such that each group's total gets progressively larger. We can achieve this efficiently by cleverly searching for the best splitting points rather than trying every possible combination. We will use an intelligent searching strategy to locate these points.

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

Calculate the total of all the numbers.
For the first group, start by considering only the first number. Gradually include more numbers until the sum of the first group is as large as possible while still being less than or equal to one-third of the total sum.
For each possible size of the first group, determine the starting point for the second group. Then, gradually add numbers to the second group until its sum is as large as possible while still being less than or equal to the total sum minus the first group's sum, divided by two.
Check if the sum of the third group (the remaining numbers) is greater than or equal to the sum of the second group. If it is, this split is valid and should be counted.
Move the starting position of the first group forward and repeat steps 2-4 to find other possible valid splits.
The total number of valid splits found during this process will be the answer.

Code Implementation

def ways_to_split_array(numbers):
    total_sum = sum(numbers)
    count_of_valid_splits = 0
    array_length = len(numbers)

    for first_group_end in range(array_length - 2):
        first_group_sum = sum(numbers[:first_group_end + 1])

        # Ensure first group sum does not exceed one third of total.
        if first_group_sum > total_sum // 3:
            break

        for second_group_end in range(first_group_end + 1, array_length - 1):
            second_group_sum = sum(numbers[first_group_end + 1:second_group_end + 1])

            # The remaining portion is implicitly the third group.
            third_group_sum = total_sum - first_group_sum - second_group_sum

            # Validate condition that third group >= second group
            if third_group_sum >= second_group_sum:
                count_of_valid_splits += 1

    return count_of_valid_splits

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates approximately up to n times, where n is the number of elements in the input array, to determine the end of the first subarray. The inner loop, for each first subarray size, iterates a variable number of times to determine the end of the second subarray. In the worst case, the inner loop's iterations are proportional to the number of remaining elements after the first subarray, so it can also go up to n times. Therefore the total number of operations approximates n * n/2, thus the time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm calculates sums and uses index variables to track split points. No auxiliary data structures like arrays, lists, or hash maps that scale with the input size N (the number of elements in the array) are created. The space used is limited to a few integer variables for sums and indices, making the auxiliary space constant regardless of the input array's size.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 if the input is null or empty, as no split is possible.
Array with fewer than 3 elements	Return 0 as a valid split into three non-empty subarrays is impossible.
Array with all identical elements	The algorithm must correctly count splits even when all elements are the same.
Array with very large numbers that might cause overflow when summing	Use appropriate data types (long, BigInteger) to prevent integer overflow during sum calculations.
No valid split exists where the sums satisfy the condition	Return 0 when no split is possible.
Extreme boundary values (very large positive or negative numbers)	Ensure the chosen data types can accommodate the range of values without overflow or underflow.
Large array size affecting performance	Optimize the search for valid split points, potentially using binary search if prefix sums are utilized.
Array contains negative numbers	The condition of subarray sum relationship must hold true regardless of element signs.

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 are the possible value ranges for the elements in the input array?
Can the input array be empty or contain only one or two elements? If so, what should I return?
What defines a valid split? Specifically, is it acceptable for the sums of two subarrays to be equal, or must they be strictly increasing? (sum1 < sum2 < sum3)
If multiple valid splits are possible, should I return a count of all such splits, or return a single example split?
Does the array contain only integers?

Brute Force Solution

Approach

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

First, consider all possible places to make the first split in the series of numbers.
For each of those first splits, consider all possible places to make the second split. This creates your three groups.
For each set of three groups you've now created, check if the sum of the numbers in the first group is less than or equal to the sum of the numbers in the second group, and if the sum of the numbers in the second group is less than or equal to the sum of the numbers in the third group.
If both conditions are true for a particular set of three groups, we have found a valid way to split the series.
Continue checking all possible split locations until all combinations have been examined.
Keep a running total of all the valid ways you find to split the series.
The final total represents the answer.

Code Implementation

def ways_to_split_array_brute_force(numbers):
    total_ways = 0
    array_length = len(numbers)

    for first_split_index in range(array_length - 2):

        for second_split_index in range(first_split_index + 1, array_length - 1):
            # Calculate sums of the three subarrays
            first_subarray_sum = sum(numbers[:first_split_index + 1])

            second_subarray_sum = sum(numbers[first_split_index + 1:second_split_index + 1])

            third_subarray_sum = sum(numbers[second_split_index + 1:])

            # Check if the sums meet the condition
            if (first_subarray_sum <= second_subarray_sum and
                    second_subarray_sum <= third_subarray_sum):
                # Increment the count if valid
                total_ways += 1

    return total_ways

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Calculate the total of all the numbers.
For the first group, start by considering only the first number. Gradually include more numbers until the sum of the first group is as large as possible while still being less than or equal to one-third of the total sum.
For each possible size of the first group, determine the starting point for the second group. Then, gradually add numbers to the second group until its sum is as large as possible while still being less than or equal to the total sum minus the first group's sum, divided by two.
Check if the sum of the third group (the remaining numbers) is greater than or equal to the sum of the second group. If it is, this split is valid and should be counted.
Move the starting position of the first group forward and repeat steps 2-4 to find other possible valid splits.
The total number of valid splits found during this process will be the answer.

Code Implementation

def ways_to_split_array(numbers):
    total_sum = sum(numbers)
    count_of_valid_splits = 0
    array_length = len(numbers)

    for first_group_end in range(array_length - 2):
        first_group_sum = sum(numbers[:first_group_end + 1])

        # Ensure first group sum does not exceed one third of total.
        if first_group_sum > total_sum // 3:
            break

        for second_group_end in range(first_group_end + 1, array_length - 1):
            second_group_sum = sum(numbers[first_group_end + 1:second_group_end + 1])

            # The remaining portion is implicitly the third group.
            third_group_sum = total_sum - first_group_sum - second_group_sum

            # Validate condition that third group >= second group
            if third_group_sum >= second_group_sum:
                count_of_valid_splits += 1

    return count_of_valid_splits

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 if the input is null or empty, as no split is possible.
Array with fewer than 3 elements	Return 0 as a valid split into three non-empty subarrays is impossible.
Array with all identical elements	The algorithm must correctly count splits even when all elements are the same.
Array with very large numbers that might cause overflow when summing	Use appropriate data types (long, BigInteger) to prevent integer overflow during sum calculations.
No valid split exists where the sums satisfy the condition	Return 0 when no split is possible.
Extreme boundary values (very large positive or negative numbers)	Ensure the chosen data types can accommodate the range of values without overflow or underflow.
Large array size affecting performance	Optimize the search for valid split points, potentially using binary search if prefix sums are utilized.
Array contains negative numbers	The condition of subarray sum relationship must hold true regardless of element signs.