This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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

- 0 < i, i + 1 < j, j + 1 < k < n - 1
- Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal.

**Example:**

Input:[1,2,1,2,1,2,1]Output:TrueExplanation: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

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

b'

\n## Solution

\n

\n#### Approach #1 Brute Force [Time Limit Exceeded]

\n

\n#### Approach #2 Cumulative Sum [Time Limit Exceeded]

\n

\n#### Approach #3 Slightly Better Approach [Time Limit Exceeded]

\n

\n#### Approach #4 Using HashMap [Time limit Exceeded]

\n

\n#### Approach #5 Using Cumulative Sum and HashSet [Accepted]

\n

\n

'
\n\n

\n\n

**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.

\n\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\n**Complexity Analysis**

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

\n

**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.

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . Three for loops are there, one within the other.

\n \n - \n
Space complexity : . array of size is used for storing cumulative sum.

\n \n

\n

**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.

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . Three loops are there.

\n \n - \n
Space complexity : . array of size is used for storing the cumulative sum.

\n \n

\n

**Algorithm**

In 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\n**Complexity Analysis**

- \n
- \n
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].

\n \n - \n
Space complexity : . HashMap size can go upto .

\n \n

\n

**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().

\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\n**Complexity Analysis**

- \n
- \n
Time complexity : . One outer loop and two inner loops are used.

\n \n - \n
Space complexity : . HashSet size can go upto .

\n \n

\n

Analysis written by: @vinod23

\n