Jobs

Interviews

Discussions

Split Array with Equal Sum

#3 Most AskedHard

Split Array with Equal Sum #3 Most Asked

Hard

Alibaba

5 views

Topics:

Arrays

Given an integer array nums of size n, you need to find if there are triplets (i, j, k) which satisfy the following conditions:

0 < i, i + 1 < j, j + 1 < k < n - 1
The sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) is equal.

Here, sum(l, r) represents the sum of the elements of nums between indices l and r inclusive.

Example 1:

Input: nums = [1,2,1,2,1,2,1]
Output: true
Explanation:
i = 1, j = 3, k = 5. 
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

Example 2:

Input: nums = [1,2,3,4,5]
Output: false

Constraints:

1 <= nums.length <= 2000
-10⁶ <= nums[i] <= 10⁶

Try coding it in LeetCode

Split Array with Equal Sum

#3 Most AskedHard

Split Array with Equal Sum #3 Most Asked

Hard

Alibaba

5 views

Topics:

Arrays

Given an integer array nums of size n, you need to find if there are triplets (i, j, k) which satisfy the following conditions:

0 < i, i + 1 < j, j + 1 < k < n - 1
The sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) is equal.

Here, sum(l, r) represents the sum of the elements of nums between indices l and r inclusive.

Example 1:

Input: nums = [1,2,1,2,1,2,1]
Output: true
Explanation:
i = 1, j = 3, k = 5. 
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

Example 2:

Input: nums = [1,2,3,4,5]
Output: false

Constraints:

1 <= nums.length <= 2000
-10⁶ <= nums[i] <= 10⁶

Try coding it in LeetCode

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 should I do if the input array is empty or contains only a single element?
Can the integers in the array be negative or zero?
Could the sums be very large, potentially causing integer overflow issues if I use a standard 32-bit integer?
To clarify the split, is the element at the split index itself included in the left subarray, the right subarray, or neither?
The problem asks for two non-empty subarrays. Does this imply that the split index cannot be the very first or the very last index of the array?

Brute Force Solution

Approach

The brute force strategy is like trying every single possible way to cut a list of numbers into four smaller pieces. For each possible set of cuts, we check if the sum of numbers in all four resulting pieces is the same.

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

First, we need to make three cuts in the list of numbers to create four smaller lists.
Let's imagine our first cut. We can try placing this cut after the first number, then after the second number, and so on, trying every possible spot for the first cut.
For each place we try for the first cut, we then need to decide where to put the second cut. We try every possible spot for the second cut that comes after the first one.
Similarly, for each combination of the first two cuts, we try every possible location for the third cut, making sure it comes after the second one.
Once we have made three cuts, we have four separate groups of numbers.
For each complete set of three cuts, we calculate the sum of the numbers in the first group, the second group, the third group, and the fourth group.
We then check if the sums of all four groups are exactly equal.
If they are equal, we've found a valid way to split the list, and we know it's possible. If we try every single combination of three cuts and never find one where the four sums are equal, then it's not possible.

Code Implementation

def split_array_with_equal_sum_brute_force(numbers):
    number_of_elements = len(numbers)

    # The first cut can be placed at any index starting from 1 up to n-6 to leave space for other cuts and subarrays.

    for first_cut_index in range(1, number_of_elements - 5):

        # The second cut must be placed at least two positions after the first to ensure a non-empty second subarray.

        for second_cut_index in range(first_cut_index + 2, number_of_elements - 3):

            # The third cut must be placed at least two positions after the second for a non-empty third subarray.

            for third_cut_index in range(second_cut_index + 2, number_of_elements - 1):
                
                # Calculate the sum for each of the four subarrays defined by the three cuts.

                first_subarray_sum = sum(numbers[0:first_cut_index])
                second_subarray_sum = sum(numbers[first_cut_index + 1:second_cut_index])
                third_subarray_sum = sum(numbers[second_cut_index + 1:third_cut_index])
                fourth_subarray_sum = sum(numbers[third_cut_index + 1:number_of_elements])

                # If all four subarray sums are equal, we have found a valid split.

                if first_subarray_sum == second_subarray_sum and second_subarray_sum == third_subarray_sum and third_subarray_sum == fourth_subarray_sum:
                    return True

    return False

Big(O) Analysis

Time Complexity

O(n³) – The time complexity is determined by the three nested loops used to place the three cuts. The first loop iterates through all possible positions for the first cut, which is roughly n possibilities. For each of these, the second loop iterates through all subsequent positions for the second cut, and similarly, the third loop iterates through positions for the third cut. This nested structure of trying every combination of three cut points results in a total number of operations proportional to n * n * n, which simplifies to O(n³).

Space Complexity

O(1) – The brute force approach iterates through all possible cut positions using nested loops, with variables to track the loop indices and the sums of the four resulting subarrays. Since these sums and indices require only a fixed number of variables regardless of the input array's size N, the auxiliary space used is constant.

Optimal Solution

Approach

The core idea is to efficiently find the three necessary cutting points that divide the list of numbers into four groups with the same sum. We can speed this up by first calculating the running total of all numbers, which allows us to instantly find the sum of any group of numbers.

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

First, create a list of running totals. The first number in this new list is the first number from the original list, the second is the sum of the first two original numbers, the third is the sum of the first three, and so on. This lets us quickly calculate the sum of any section of the original list.
Next, we need to pick the middle cutting point. We'll try every possible position for this middle cut, one by one.
For each potential middle cut, we know the sum of all the numbers to its left and all the numbers to its right.
Now, look at the left side. We need to find a first cutting point that splits this left section into two smaller groups of equal size. We can check every possible spot for this first cut.
If we find a valid first cut on the left side, we remember the sum of the small group it created. We should keep track of all possible sums we can create this way on the left side.
Then, we look at the right side of the middle cut. We search for a third cutting point that splits this right section into two smaller groups of equal size.
If we find a valid third cut on the right, we check if the sum of the small group it creates is a sum we've already seen and stored from our search on the left side.
If we find a match – meaning we found a first cut, a middle cut, and a third cut that all result in four groups with the exact same sum – we've succeeded and can stop.
If we try every possible middle cut and never find a set of three cuts that works, then it's impossible to split the list as required.

Code Implementation

def split_array_with_equal_sum(list_of_numbers):
    number_count = len(list_of_numbers)
    if number_count < 7:
        return False

    # Pre-calculating prefix sums allows for O(1) lookups of subarray sums.
    prefix_sums = [0] * number_count
    prefix_sums[0] = list_of_numbers[0]
    for index in range(1, number_count):
        prefix_sums[index] = prefix_sums[index - 1] + list_of_numbers[index]

    # We iterate through all possible middle cut positions.
    for middle_cut_index in range(3, number_count - 3):
        left_side_sums = set()
        # Find a valid first cut that splits the left part into two equal sum subarrays.
        for first_cut_index in range(1, middle_cut_index - 1):
            first_group_sum = prefix_sums[first_cut_index - 1]
            second_group_sum = prefix_sums[middle_cut_index - 1] - prefix_sums[first_cut_index]
            if first_group_sum == second_group_sum:
                left_side_sums.add(first_group_sum)

        if not left_side_sums:
            continue

        # Now check the right side for a third cut that creates an equal sum we've seen on the left.
        for third_cut_index in range(middle_cut_index + 2, number_count - 1):
            third_group_sum = prefix_sums[third_cut_index - 1] - prefix_sums[middle_cut_index]
            fourth_group_sum = prefix_sums[number_count - 1] - prefix_sums[third_cut_index]
            if third_group_sum == fourth_group_sum and third_group_sum in left_side_sums:
                return True

    return False

Big(O) Analysis

Time Complexity

O(n²) – The initial step of creating a list of running totals takes O(n) time. The main part of the algorithm involves an outer loop that iterates through all possible middle cutting points, which runs approximately n times. Inside this loop, we have two separate, non-nested loops: one to find all possible first cutting points on the left side and another to find all possible third cutting points on the right. In the worst case, each of these inner loops also runs up to n times, leading to a total complexity driven by the nested structure of the middle cut loop and the left-side search loop. This results in approximately n * n operations, which simplifies to a time complexity of O(n²).

Space Complexity

O(N) – The primary source of extra memory is the list of running totals, or prefix sums, created in the first step, which has a size directly proportional to the input list's size, N. The second significant data structure is the set used to store all valid sums found on the left side of the middle cut. In the worst-case scenario, this set could also store up to O(N) distinct sum values. Therefore, the total auxiliary space complexity is dominated by these two structures, resulting in O(N).

Edge Cases

Case	How to Handle
Empty array or a null input	Return -1 immediately as no valid split is possible.
Array with one or two elements	Return -1 because it's impossible to form two non-empty subarrays around a split index.
Array containing only zeros	The first valid index, which is 1, should be returned as any split will result in sums of zero.
Array with negative numbers and positive numbers that cancel out	The prefix sum approach correctly handles both negative and positive values without special logic.
No valid split index exists	If the loop completes without finding an index where left sum equals right sum, return -1.
Multiple valid split indices exist	The solution should iterate from left to right and return the very first valid index it finds.
Large array with very large numbers	Use a 64-bit integer type (like 'long' in Java or Python's arbitrary-precision integers) for sum calculations to prevent integer overflow.
The split occurs at the first or last possible position	The solution must correctly check the edge conditions, such as a split at index 1 or index n-2.

Empty array or a null input

How to Handle:

Return -1 immediately as no valid split is possible.

Array with one or two elements

How to Handle:

Return -1 because it's impossible to form two non-empty subarrays around a split index.

Array containing only zeros

How to Handle:

The first valid index, which is 1, should be returned as any split will result in sums of zero.

Array with negative numbers and positive numbers that cancel out

How to Handle:

The prefix sum approach correctly handles both negative and positive values without special logic.

No valid split index exists

How to Handle:

If the loop completes without finding an index where left sum equals right sum, return -1.

Multiple valid split indices exist

How to Handle:

The solution should iterate from left to right and return the very first valid index it finds.

Large array with very large numbers

How to Handle:

Use a 64-bit integer type (like 'long' in Java or Python's arbitrary-precision integers) for sum calculations to prevent integer overflow.

The split occurs at the first or last possible position

How to Handle:

The solution must correctly check the edge conditions, such as a split at index 1 or index n-2.

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 should I do if the input array is empty or contains only a single element?
Can the integers in the array be negative or zero?
Could the sums be very large, potentially causing integer overflow issues if I use a standard 32-bit integer?
To clarify the split, is the element at the split index itself included in the left subarray, the right subarray, or neither?
The problem asks for two non-empty subarrays. Does this imply that the split index cannot be the very first or the very last index of the array?

Brute Force Solution

Approach

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

First, we need to make three cuts in the list of numbers to create four smaller lists.
Let's imagine our first cut. We can try placing this cut after the first number, then after the second number, and so on, trying every possible spot for the first cut.
For each place we try for the first cut, we then need to decide where to put the second cut. We try every possible spot for the second cut that comes after the first one.
Similarly, for each combination of the first two cuts, we try every possible location for the third cut, making sure it comes after the second one.
Once we have made three cuts, we have four separate groups of numbers.
For each complete set of three cuts, we calculate the sum of the numbers in the first group, the second group, the third group, and the fourth group.
We then check if the sums of all four groups are exactly equal.
If they are equal, we've found a valid way to split the list, and we know it's possible. If we try every single combination of three cuts and never find one where the four sums are equal, then it's not possible.

Code Implementation

def split_array_with_equal_sum_brute_force(numbers):
    number_of_elements = len(numbers)

    # The first cut can be placed at any index starting from 1 up to n-6 to leave space for other cuts and subarrays.

    for first_cut_index in range(1, number_of_elements - 5):

        # The second cut must be placed at least two positions after the first to ensure a non-empty second subarray.

        for second_cut_index in range(first_cut_index + 2, number_of_elements - 3):

            # The third cut must be placed at least two positions after the second for a non-empty third subarray.

            for third_cut_index in range(second_cut_index + 2, number_of_elements - 1):
                
                # Calculate the sum for each of the four subarrays defined by the three cuts.

                first_subarray_sum = sum(numbers[0:first_cut_index])
                second_subarray_sum = sum(numbers[first_cut_index + 1:second_cut_index])
                third_subarray_sum = sum(numbers[second_cut_index + 1:third_cut_index])
                fourth_subarray_sum = sum(numbers[third_cut_index + 1:number_of_elements])

                # If all four subarray sums are equal, we have found a valid split.

                if first_subarray_sum == second_subarray_sum and second_subarray_sum == third_subarray_sum and third_subarray_sum == fourth_subarray_sum:
                    return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, create a list of running totals. The first number in this new list is the first number from the original list, the second is the sum of the first two original numbers, the third is the sum of the first three, and so on. This lets us quickly calculate the sum of any section of the original list.
Next, we need to pick the middle cutting point. We'll try every possible position for this middle cut, one by one.
For each potential middle cut, we know the sum of all the numbers to its left and all the numbers to its right.
Now, look at the left side. We need to find a first cutting point that splits this left section into two smaller groups of equal size. We can check every possible spot for this first cut.
If we find a valid first cut on the left side, we remember the sum of the small group it created. We should keep track of all possible sums we can create this way on the left side.
Then, we look at the right side of the middle cut. We search for a third cutting point that splits this right section into two smaller groups of equal size.
If we find a valid third cut on the right, we check if the sum of the small group it creates is a sum we've already seen and stored from our search on the left side.
If we find a match – meaning we found a first cut, a middle cut, and a third cut that all result in four groups with the exact same sum – we've succeeded and can stop.
If we try every possible middle cut and never find a set of three cuts that works, then it's impossible to split the list as required.

Code Implementation

def split_array_with_equal_sum(list_of_numbers):
    number_count = len(list_of_numbers)
    if number_count < 7:
        return False

    # Pre-calculating prefix sums allows for O(1) lookups of subarray sums.
    prefix_sums = [0] * number_count
    prefix_sums[0] = list_of_numbers[0]
    for index in range(1, number_count):
        prefix_sums[index] = prefix_sums[index - 1] + list_of_numbers[index]

    # We iterate through all possible middle cut positions.
    for middle_cut_index in range(3, number_count - 3):
        left_side_sums = set()
        # Find a valid first cut that splits the left part into two equal sum subarrays.
        for first_cut_index in range(1, middle_cut_index - 1):
            first_group_sum = prefix_sums[first_cut_index - 1]
            second_group_sum = prefix_sums[middle_cut_index - 1] - prefix_sums[first_cut_index]
            if first_group_sum == second_group_sum:
                left_side_sums.add(first_group_sum)

        if not left_side_sums:
            continue

        # Now check the right side for a third cut that creates an equal sum we've seen on the left.
        for third_cut_index in range(middle_cut_index + 2, number_count - 1):
            third_group_sum = prefix_sums[third_cut_index - 1] - prefix_sums[middle_cut_index]
            fourth_group_sum = prefix_sums[number_count - 1] - prefix_sums[third_cut_index]
            if third_group_sum == fourth_group_sum and third_group_sum in left_side_sums:
                return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array or a null input	Return -1 immediately as no valid split is possible.
Array with one or two elements	Return -1 because it's impossible to form two non-empty subarrays around a split index.
Array containing only zeros	The first valid index, which is 1, should be returned as any split will result in sums of zero.
Array with negative numbers and positive numbers that cancel out	The prefix sum approach correctly handles both negative and positive values without special logic.
No valid split index exists	If the loop completes without finding an index where left sum equals right sum, return -1.
Multiple valid split indices exist	The solution should iterate from left to right and return the very first valid index it finds.
Large array with very large numbers	Use a 64-bit integer type (like 'long' in Java or Python's arbitrary-precision integers) for sum calculations to prevent integer overflow.
The split occurs at the first or last possible position	The solution must correctly check the edge conditions, such as a split at index 1 or index n-2.

Empty array or a null input

How to Handle:

Return -1 immediately as no valid split is possible.

Array with one or two elements

How to Handle:

Return -1 because it's impossible to form two non-empty subarrays around a split index.

Array containing only zeros

How to Handle:

The first valid index, which is 1, should be returned as any split will result in sums of zero.

Array with negative numbers and positive numbers that cancel out

How to Handle:

The prefix sum approach correctly handles both negative and positive values without special logic.

No valid split index exists

How to Handle:

If the loop completes without finding an index where left sum equals right sum, return -1.

Multiple valid split indices exist

How to Handle:

The solution should iterate from left to right and return the very first valid index it finds.

Large array with very large numbers

How to Handle:

Use a 64-bit integer type (like 'long' in Java or Python's arbitrary-precision integers) for sum calculations to prevent integer overflow.

The split occurs at the first or last possible position

How to Handle:

The solution must correctly check the edge conditions, such as a split at index 1 or index n-2.

0/5 Alibaba questions completed

0/5 completed