Given an array with n integers, you need to find if there are triplets (i, j, k) which satisfies following conditions:
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) = 1Note:
Algorithm
\nBefore 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.
\nThus, the limits based on the length of the array can now be rewritten as:
\n\n\n
\n\n\n
\n\n\n
\nHaving 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.
\nWe 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.
\n\nComplexity Analysis
\nAlgorithm
\nIn 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.
\n\nComplexity Analysis
\nTime complexity : . Three for loops are there, one within the other.
\nSpace complexity : . array of size is used for storing cumulative sum.
\nAlgorithm
\nWe 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.
\n\nComplexity Analysis
\nTime complexity : . Three loops are there.
\nSpace complexity : . array of size is used for storing the cumulative sum.
\nAlgorithm
\nIn this approach, we create a data structure called which is simply a HashMap, with data arranged in the format:
\n\n, here represents the cumulative sum in the given array upto the index and its corresponding value represents indices upto which cumulative sum=csum(i).
\nOnce 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:
\n\n.
\nThus, 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.
\nFollowing the similar lines as the discussion above, the cumulative sum upto the third cut by index is given by
\n\n.
\nFor equality of sum, the condition becomes:
\n\n.
\nSimilarly, the cumulative sum upto the last index becomes:
\n\n.
\nAgain, for equality, the condition becomes:
\n\n.
\nFor 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.
\n\nComplexity Analysis
\nTime 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].
\nSpace complexity : . HashMap size can go upto .
\nAlgorithm
\nIn 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().
\nThen, 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.
\nLook at the animation below for a visual representation of the process:
\n\n!?!../Documents/548_Split_Array.json:1000,563!?!
\n\nComplexity Analysis
\nTime complexity : . One outer loop and two inner loops are used.
\nSpace complexity : . HashSet size can go upto .
\nAnalysis written by: @vinod23
\n