Split Array with Equal Sum

Problem Statement

In this problem, you are given an integer array nums with a length n. The task is to determine whether there exists a triplet of indices (i, j, k) within the array such that specific conditions are met related to the sum of the values of subarrays divided by these indices. The conditions for the indices are:

• The indices adhere to specific positions: 0 < i, i + 1 < j, j + 1 < k < n - 1.
• The sum of the subarrays (0, i-1), (i+1, j-1), (j+1, k-1), and (k+1, n-1) are equal, where each subarray represents a segment of the original array starting from index l to r, inclusive.

The objective is to return true if such a triplet is found, otherwise false.

Examples

Example 1

Input:

nums = [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

Example 2

Input:

nums = [1,2,1,2,1,2,1,2]

Output:

false

Constraints

• n == nums.length
• 1 <= n <= 2000
• -106 <= nums[i] <= 106

Approach and Intuition

To solve this problem, understanding both the constraints and the desired subarray sums is crucial. A detailed analysis of the problem reveals that we can leverage the properties of prefix sums which helps in efficient computation of the sum of elements in any subarray given a start and end index. Follow these steps for a potential solution approach:

1. Compute the prefix sum for the entire array first. The prefix sum array will be used to quickly compute the sum of any subarray in constant time.
2. Establish the outer most loops for indices i and k. The main idea is to fix i and k first and then try to find a suitable j that satisfies the condition of having equal subarray sums around i and k.
3. When i is fixed, calculate the sum of the potential first subarray represented by (0, i-1).
4. Similarly, fix k and compute the sum of the potential last subarray represented by (k+1, n-1).
5. Iterate through possible values of j between i + 1 and k - 1 to check if the remaining two middle subarrays (i+1, j-1) and (j+1, k-1) have equal sums.
6. If all four subarray sums (0, i-1), (i+1, j-1), (j+1, k-1), (k+1, n-1) are equal while iterating, immediately return true.
7. If the end of the loop is reached without finding such a triplet, return false.

This method ensures a structured way to check each potential triplet without unnecessary recalculations of subarray sums, utilizing the prefix sum for efficiency. This approach ideally exploits the possibility of early exits as soon as a valid triplet is found, enhancing performance especially for large arrays up to the constraint limits.

Solutions

public class Solution {
    public boolean canPartition(int[] arr) {
        if (arr.length < 7)
            return false;
        int[] prefixSum = new int[arr.length];
        prefixSum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }
        for (int mid = 3; mid < arr.length - 3; mid++) {
            HashSet<Integer> seenSums = new HashSet<>();
            for (int left = 1; left < mid - 1; left++) {
                if (prefixSum[left - 1] == prefixSum[mid - 1] - prefixSum[left])
                    seenSums.add(prefixSum[left - 1]);
            }
            for (int right = mid + 2; right < arr.length - 1; right++) {
                if (prefixSum[arr.length - 1] - prefixSum[right] == prefixSum[right - 1] - prefixSum[mid] && seenSums.contains(prefixSum[right - 1] - prefixSum[mid]))
                    return true;
            }
        }
        return false;
    }
}