Split Array With Equal Sums
You are given an array/list 'ARR' of size 'N'. You task is to find if there exists a triplet (i, j, k) such that 0

Question

Split Array With Equal Sums

You are given an array/list 'ARR' of size 'N'. You task is to find if there exists a triplet (i, j, k) such that 0 < i , i + 1 < j , j + 1 < k and k < 'N' - 1 and the sum of the subarrays [0, i - 1],[i + 1, j - 1], [j + 1, k - 1], [k + 1, N - 1] are equal.

An array c is a subarray of array d if c can be obtained from d by deletion of several elements from the beginning and several elements from the end.

Example:

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

Note: Assume That the Array has Zero-based indexing.

Input format:

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.

Output format:

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.

Note:

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

Constraints:

1 <= T <= 5
1 <= N <= 10 ^ 3
-10 ^ 6 <= ARR[i] <= 10 ^ 6

Time Limit: 1 sec

Accepted Answer

Brute Force

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’.
If we do not find any valid triplet we return ‘False’.

Space Complexity: O(1)Explanation:

O(1)

Because, Constant space is used.

Time Complexity: O(n^4)Explanation:

O(N^4), where N is the size of ARR.

We are iterating over all possible i, j and k in O(N^3) time complexity. For each possible i, j and k we are finding the sum of the subarray in O(N) time complexity. Hence overall time complexity will be O(N^4).

Python (3.5)

'''

    Time complexity: O(N^4)

    Space Complexity: O(N)



    where N is the size of array/list nums.

'''



def splitArray(nums, n):

    

    if (n < 7):

        return False

    

    for i in range(1, n - 5):

        sum1 = 0

        for temp in range(i):

            sum1 += nums[temp]



        for j in range(i + 2, n - 3):

            sum2 = 0

            for temp in range(i + 1, j):

                sum2 += nums[temp]

        

            for k in range(j + 2, n - 1):

                sum3 = 0

                for temp in range(j + 1, k):

                    sum3 += nums[temp]   

                sum4 = 0

                for temp in range(k + 1, n):

                    sum4 += nums[temp]

            

                if (sum1 == sum2) and (sum2 == sum3) and (sum3 == sum4):

                    return True



    return False

Java (SE 1.8)

/*
    Time complexity: O(N^4)
    Space Complexity: O(N)

    where N is the size of array/list nums.
*/

public class Solution {
    public static Boolean splitArray(int[] nums, int n) {
        
        if (n < 7) {
            return false;
        }

        for (int i = 1; i < n - 5; ++i) {

            int sum1 = 0;
            for (int temp = 0; temp <= i - 1; temp++) {
                sum1 += nums[temp];
            }

            for (int j = i + 2; j < n - 3; ++j) {

                int sum2 = 0;
                for (int temp = i + 1; temp <= j - 1; temp++) {
                    sum2 += nums[temp];
                }

                for (int k = j + 2; k < n - 1; ++k) {

                    int sum3 = 0;
                    for (int temp = j + 1; temp <= k - 1; temp++) {
                        sum3 += nums[temp];
                    }
                    int sum4 = 0;
                    for (int temp = k + 1; temp < n; temp++) {
                        sum4 += nums[temp];
                    }

                    if (sum1 == sum2 && sum2 == sum3 && sum3 == sum4) {
                        return true;
                    }

                }
            }
        }
        return false;
    }
}

C++ (g++ 5.4)

/*
    Time complexity: O(N^4)
    Space Complexity: O(N)

    where N is the size of array/list nums.
*/

bool splitArray(vector < int > & nums, int n) {

    if (n < 7) {
        return false;
    }

    for (int i = 1; i < n - 5; ++i) {

        int sum1 = 0;
        for (int temp = 0; temp <= i - 1; temp++) {
            sum1 += nums[temp];
        }

        for (int j = i + 2; j < n - 3; ++j) {

            int sum2 = 0;
            for (int temp = i + 1; temp <= j - 1; temp++) {
                sum2 += nums[temp];
            }

            for (int k = j + 2; k < n - 1; ++k) {

                int sum3 = 0;
                for (int temp = j + 1; temp <= k - 1; temp++) {
                    sum3 += nums[temp];
                }
                int sum4 = 0;
                for (int temp = k + 1; temp < n; temp++) {
                    sum4 += nums[temp];
                }

                if (sum1 == sum2 && sum2 == sum3 && sum3 == sum4) {
                    return true;
                }

            }
        }
    }
    return false;

}

Accepted Answer

Using Prefix Sum

This one is the optimization to the Brute force approach. We will iterate over all possible ‘i’ , ‘j’ and ‘k’ and for each possible subarray instead of calculating it’s sum in O(N) time complexity we can get in O(1) time complexity using prefix sums and pre calculation.

Space Complexity: O(n)Explanation:

O(N), where N is the size of ARR.

The space complexity due to the array/list of prefix sum will be O(N).

Time Complexity: O(n^3)Explanation:

O(N^3), where N is the size of ARR.

We are iterating over all possible i, j and k in O(N^3) time complexity. For each possible i, j and k we are finding the sum of the subarray in O(1) time complexity. Hence overall time complexity will be O(N^3).

Python (3.5)

'''
    Time complexity: O(N^3)
    Space Complexity: O(N)

    where N is the size of the array/list nums.
'''

def splitArray(nums, n):

    if(n < 7):
        return False

    # Store prefix sum in the sum vector.
    sum = []

    sum.append(nums[0])

    for i in range(1, n):
        sum.append(sum[i - 1] + nums[i])

    # Check all the possible triplets and corresponding sum.
    for i in range(1, n - 5):

        sum1 = sum[i - 1]

        for j in range(i + 2, n - 3):

            sum2 = sum[j - 1] - sum[i]

            for k in range(j + 2, n - 1):

                sum3 = sum[k - 1] - sum[j]
                sum4 = sum[n - 1] - sum[k]

                if(sum1 == sum2 and sum2 == sum3 and sum3 == sum4):
                    return True
                
    return False

C++ (g++ 5.4)

/*
    Time complexity: O(N^3)
    Space Complexity: O(N)

    where N is the size of array/list nums.
*/

bool splitArray(vector &nums,   int n){

    if(n < 7){
        return false;
    }

    // Store prefix sum in the sum vector.
    vector sum;

    sum.push_back(nums[0]);

    for (int i = 1; i < n; i++){
        sum.push_back(sum[i - 1] + nums[i]);
    }

    // Check all the possible triplets and corresponding sum.
    for (int i = 1; i < n - 5; ++i){

        int sum1 = sum[i - 1];

        for (int j = i + 2; j < n - 3; ++j){

            int sum2 = sum[j - 1] - sum[i];

            for (int k = j + 2; k < n - 1; ++k){

                int sum3 = sum[k - 1] - sum[j];
                int sum4 = sum[n - 1] - sum[k];

                if(sum1==sum2 && sum2==sum3 && sum3==sum4){
                    return true;
                }

            }
        }
    }
    
    return false;

}

Java (SE 1.8)

/*
    Time complexity: O(N^3)
    Space Complexity: O(N)

    where N is the size of array/list nums.
*/

import java.util.ArrayList;

public class Solution {
    public static Boolean splitArray(int[] nums, int n) {
        
        if(n < 7){
            return false;
        }

        // Store prefix sum in the sum Arraylist.
        ArrayList sum = new ArrayList();

        sum.add(nums[0]);

        for (int i = 1; i < n; i++){
            sum.add(sum.get(i - 1) + nums[i]);
        }

        // Check all the possible triplets and corresponding sum.
        for (int i = 1; i < n - 5; ++i){

            int sum1 = sum.get(i - 1);

            for (int j = i + 2; j < n - 3; ++j){

                int sum2 = sum.get(j - 1) - sum.get(i);

                for (int k = j + 2; k < n - 1; ++k){

                      int sum3 = sum.get(k - 1) - sum.get(j);
                      int sum4 = sum.get(n - 1) - sum.get(k);

                    if(sum1==sum2 && sum2==sum3 && sum3==sum4){
                        return true;
                    }

                }
            }
        }

        return false;
    }
}

Accepted Answer

Using Unordered Set

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

Space Complexity: O(n)Explanation:

O(N), where N is the size of ARR.

The space complexity due to the hashmap will be O(N) in the worst case.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the size of ARR.

We are iterating over all possible values of j in O(N) time complexity. Now for every j, we are iterating overall i and k in O(N) time complexity. Hence overall time complexity will be O(N^2). The time complexity due to the hashmap will be O(1).

Python (3.5)

'''
    Time complexity: O(N^2)
    Space Complexity: O(N)

    Where N is the size of the array/list nums.
'''

def splitArray(nums, n):

    if n < 7:
        return False
    
    sum = []
    sum.append(nums[0])

    # Storing prefix sum in the list sum.
    for i in range(1, n):
        sum.append(sum[i - 1] + nums[i])

    for j in range(3 , n - 3):

        '''
            Store the equal sum part of left side in set to 
            to check them in right part of the array.
        '''
        store = set()

        for i in range(1, j - 1):
            if sum[i - 1] == sum[j - 1] - sum[i]:
                store.add(sum[i - 1])

        for k in range(j + 2, n - 1):

            # If the sum of two parts are equal & that value exits in set,then return true.
            if sum[n - 1] - sum[k] == sum[k - 1] - sum[j]:
                if sum[n - 1] - sum[k] in store:
                    return True

    return False

C++ (g++ 5.4)

/*
    Time complexity: O(N^2)
    Space Complexity: O(N)

    Where N is the size of the array/list nums.
*/

#include 

bool splitArray(vector < int > & nums, int n) {

    if (n < 7) {
        return false;
    }

    vector < int > sum;

    // Storing prefix sum in the vector sum.
    sum.push_back(nums[0]);

    for (int i = 1; i < n; ++i) {
        sum.push_back(sum[i - 1] + nums[i]);
    }

    for (int j = 3; j < n - 3; ++j) {

        /*
            Store the equal sum part of left side in set to 
            to check them in right part of the array.
        */

        unordered_set < int > store;

        for (int i = 1; i < j - 1; ++i) {

            if (sum[i - 1] == sum[j - 1] - sum[i]) {
                store.insert(sum[i - 1]);
            }
        }

        for (int k = j + 2; k < n - 1; ++k) {

            // If the sum of two parts are equal & that value exits in set,then return true.
            if (sum[n - 1] - sum[k] == sum[k - 1] - sum[j] && store.count(sum[n - 1] - sum[k])) {
                return true;
            }
        }
    }

    return false;
}

Java (SE 1.8)

/*
    Time complexity: O(N^2)
    Space Complexity: O(N)

    Where N is the size of the array/list nums.
*/

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public static Boolean splitArray(int[] nums, int n) {

        if(n < 7){
            return false;
        }

        // Store prefix sum in the sum Arraylist.
        ArrayList sum = new ArrayList();

        sum.add(nums[0]);

        for (int i = 1; i < n; i++){
            sum.add(sum.get(i - 1) + nums[i]);
        }

        for (int j = 3; j < n - 3; ++j){

            /*
                Store the equal sum part of left side in set to 
                to check them in right part of the array.
            */

            Set store = new HashSet();

            for (int i = 1; i < j - 1; ++i){

                if(sum.get(i - 1) == sum.get(j - 1) - sum.get(i)){
                    store.add(sum.get(i-1));
                }
            }

            for (int k = j + 2; k < n - 1; ++k){

                // If the sum of two parts are equal & that value exits in set,then return true.
                if(sum.get(n - 1) - sum.get(k) == sum.get(k - 1) - sum.get(j) && store.contains(sum.get(n - 1) - sum.get(k))){
                    return true;
                }
            }
        }

        return false;

    }
}

You are given an array/list 'ARR' of size 'N'. You task is to find if there exists a triplet (i, j, k) such that 0 < i , i + 1 < j , j + 1 < k and k < 'N' - 1 and the sum of the subarrays [0, i - 1],[i + 1, j - 1], [j + 1, k - 1], [k + 1, N - 1] are equal.

An array c is a subarray of array d if c can be obtained from d by deletion of several elements from the beginning and several elements from the end.

Example:

Note: Assume That the Array has Zero-based indexing.

Input format:

Output format:

Note:

Constraints:

Popular interview questions of Software Developer Intern