New update is available. Click here to update.

Last Updated: 5 Mar, 2021

Difficulty: Moderate

```
let 'ARR' = [1, 2, 3] then the possible subarrays of 'ARR' will be - {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}.
```

```
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains an integer ‘N’ representing the array’s size.
The second line of each test case contains 'N' space-separated integers representing the array’s elements.
```

```
For each test case, print ‘True’ if such a triplet exists; else print ‘False’.
Output for each test case will be printed in a separate line.
```

```
You don’t have to take any input or print anything; it already has been taken care of. Just implement the function.
```

```
1 <= T <= 5
1 <= N <= 10 ^ 3
-10 ^ 6 <= ARR[i] <= 10 ^ 6
Time Limit: 1 sec
```

To implement this approach, You have to understand the constraints first, i.e., 0 < i, i+1 < j , j+1< k < N-1.

If you carefully look at the constraints, you may notice the problem while splitting the array into slices or subarrays does not include the elements at index i, j, and k. So it can be simply observed that according to constraints during the slices you make, three of the elements will not get included in any of the slices. Every Slice needs to be non-empty, too, so your task is to make four of these partitions. You can conclude from these points that the array size should be at least 7 to find such a triplet, any size below 7 will result in ‘False’.

To simplify this we can write this as:

0 < i < N - 5

i + 1 < j < N - 3

j + 1 < k < N - 1

The algorithm will be:

- We can iterate over each ‘i’ from 1 to ‘N’ - 5:
- Now for each ‘j’ from ‘i’ + 1 to ‘N’ - 3:
- Now for each 'k' from 'j' + 1 to 'N' - 1:
- We can calculate the sum for each of the above-formed subarray in one iteration.
- If the sum of the subarrays is equal we return ‘True’.

- Now for each 'k' from 'j' + 1 to 'N' - 1:

- Now for each ‘j’ from ‘i’ + 1 to ‘N’ - 3:
- If we do not find any valid triplet we return ‘False’.

You can do this by first dividing the arraylist in two equal sums and then further dividing the first half in two equal sums and then checking the remaining half for these sums.

- Initially store the prefix sum of the array in a separate array.
- For all the possible j
- Check the value for which the sum of the right half and the left half is equal.
- Now for all possible values of i in the left half.
- Check for the equal half sums, and store the sum in a hash map.

- Now for each possible k in the right half.
- Check for the equal half sums, and store the sum in a hash map.

- If any common value is found in both of the hashmaps we return ‘True’.
- If no valid triplet is found we return ‘False’.

SIMILAR PROBLEMS

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Maximum GCD

Posted: 8 Dec, 2022

Difficulty: Hard

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Popular Interview Problems: