548. Split Array with Equal Sum


Given an array with n integers, you need to find if there are triplets (i, j, k) which satisfies following conditions:

  1. 0 < i, i + 1 < j, j + 1 < k < n - 1
  2. Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal.
where we define that subarray (L, R) represents a slice of the original array starting from the element indexed L to the element indexed R.

Example:

Input: [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

Note:
  1. 1 <= n <= 2000.
  2. Elements in the given array will be in range [-1,000,000, 1,000,000].

Solution

Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

Before we start looking at any of the approaches for solving this problem, firstly we need to look at the limits imposed on , and by the given set of constraints. The figure below shows the maximum and minimum values that , and can assume.

Split_Array

Thus, the limits based on the length of the array can now be rewritten as:

Having discussed the limits imposed on the cuts , , that we will apply on the given array , let's look at the first solution that comes to our mind.

We simply traverse over all the elements of the array. We consider all the possible subarrays taking care of the constraints imposed on the cuts, and check if any such cuts exist which satisfy the given equal sum quadruples criteria.

Complexity Analysis

  • Time complexity : . Four for loops inside each other each with a worst case run of length .
  • Space complexity : . Constant Space required.

Approach #2 Cumulative Sum [Time Limit Exceeded]

Algorithm

In the brute force approach, we traversed over the subarrays for every triplet of cuts considered. Rather than doing this, we can save some calculation effort if we make use of a cumulative sum array , where stores the cumulative sum of the array upto the element. Thus, now in order to find the , we can simply use . Rest of the process remains the same.

Complexity Analysis

  • Time complexity : . Three for loops are there, one within the other.

  • Space complexity : . array of size is used for storing cumulative sum.

Approach #3 Slightly Better Approach [Time Limit Exceeded]

Algorithm

We can improve the previous implementation to some extent if we stop checking for further quadruples if the first and second parts formed till now don't have equal sums. This idea is used in the current implementation.

Complexity Analysis

  • Time complexity : . Three loops are there.

  • Space complexity : . array of size is used for storing the cumulative sum.

Approach #4 Using HashMap [Time limit Exceeded]

Algorithm

In this approach, we create a data structure called which is simply a HashMap, with data arranged in the format:

, here represents the cumulative sum in the given array upto the index and its corresponding value represents indices upto which cumulative sum=csum(i).

Once we create this , the solutions gets simplified a lot. Consider only the first two cuts formed by and . Then, the cumulative sum upto the index will be given by: . Now, if we want the first two parts to have the same sum, the same cumulative sum can be rewritten as:

.

Thus, we traverse over the given array, changing the value of the index forming the first cut, and look if the formed initially contains a cumulative sum equal to . If contains such a cumulative sum, we consider every possible index satisfying the given constraints and look for the equalities of the first cumulative sum with the third and the fourth parts.

Following the similar lines as the discussion above, the cumulative sum upto the third cut by index is given by

.

For equality of sum, the condition becomes:

.

Similarly, the cumulative sum upto the last index becomes:

.

Again, for equality, the condition becomes:

.

For every cut chosen, we look if the required cumulative sum exists in . Thus, we need not calculate sums again and again or traverse over the array for all the triplets possible. Rather, now, we directly know, what cumulative sum to look for in the , which reduces a lot of computations.

Complexity Analysis

  • Time complexity : . Three nested loops are there and every loop runs times in the worst case. Consider the worstcase [0,0,0....,1,1,1,1,1,1,1].

  • Space complexity : . HashMap size can go upto .

Approach #5 Using Cumulative Sum and HashSet [Accepted]

Algorithm

In this approach, firstly we form a cumulative sum array , where stores the cumulative sum of the array upto the index. Then, we start by traversing over the possible positions for the middle cut formed by . For every , firstly, we find all the left cut's positions, , that lead to equalizing the sum of the first and the second part (i.e. ) and store such sums in the (a new HashSet is formed for every chosen). Thus, the presence of a sum in implies that such a sum is possible for having equal sum of the first and second part for the current position of the middle cut().

Then, we go for the right cut and find the position of the right cut that leads to equal sum of the third and the fourth part (), for the same middle cut as chosen earlier. We also, look if the same sum exists in the . If so, such a triplet exists which satisfies the required criteria, otherwise not.

Look at the animation below for a visual representation of the process:

!?!../Documents/548_Split_Array.json:1000,563!?!

Complexity Analysis

  • Time complexity : . One outer loop and two inner loops are used.

  • Space complexity : . HashSet size can go upto .

Analysis written by: @vinod23

Submit Solution