Split Array with Equal Sum

hard array prefix sum

Problem

Find i < j < k splitting nums into four parts (gaps removed) with equal sums: (0,i-1),(i+1,j-1),(j+1,k-1),(k+1,n-1).

Inputnums = [1,2,1,2,1,2,1]

Outputtrue

O(n²) by fixing j first, then a set of acceptable s on left, then checking right.

nums

def split_array(nums):
    n = len(nums)
    if n < 7: return False
    pref = [0]
    for x in nums: pref.append(pref[-1] + x)
    for j in range(3, n - 3):
        left = set()
        for i in range(1, j - 1):
            if pref[i] - pref[0] == pref[j] - pref[i + 1]:
                left.add(pref[i])
        for k in range(j + 2, n - 1):
            if pref[k] - pref[j + 1] == pref[n] - pref[k + 1] and pref[k] - pref[j + 1] in left:
                return True
    return False

function splitArray(nums) {
  const n = nums.length;
  if (n < 7) return false;
  const pref = [0];
  for (const x of nums) pref.push(pref[pref.length - 1] + x);
  for (let j = 3; j < n - 3; j++) {
    const left = new Set();
    for (let i = 1; i < j - 1; i++) {
      if (pref[i] === pref[j] - pref[i + 1]) left.add(pref[i]);
    }
    for (let k = j + 2; k < n - 1; k++) {
      const s = pref[k] - pref[j + 1];
      if (s === pref[n] - pref[k + 1] && left.has(s)) return true;
    }
  }
  return false;
}

class Solution {
    public boolean splitArray(int[] nums) {
        int n = nums.length;
        if (n < 7) return false;
        int[] pref = new int[n + 1];
        for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
        for (int j = 3; j < n - 3; j++) {
            Set left = new HashSet<>();
            for (int i = 1; i < j - 1; i++)
                if (pref[i] == pref[j] - pref[i + 1]) left.add(pref[i]);
            for (int k = j + 2; k < n - 1; k++) {
                int s = pref[k] - pref[j + 1];
                if (s == pref[n] - pref[k + 1] && left.contains(s)) return true;
            }
        }
        return false;
    }
}

bool splitArray(vector& nums) {
    int n = nums.size();
    if (n < 7) return false;
    vector pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
    for (int j = 3; j < n - 3; j++) {
        unordered_set left;
        for (int i = 1; i < j - 1; i++)
            if (pref[i] == pref[j] - pref[i + 1]) left.insert(pref[i]);
        for (int k = j + 2; k < n - 1; k++) {
            int s = pref[k] - pref[j + 1];
            if (s == pref[n] - pref[k + 1] && left.count(s)) return true;
        }
    }
    return false;
}

Explanation

We need three cut points i < j < k that split the array into four pieces (the cut elements are thrown away) all with the same sum. Trying every triple is too slow, so we fix the middle cut j first and use a prefix-sum array plus a set to make the rest fast.

With pref precomputed, any piece's sum is a quick subtraction. For a fixed j, we scan possible left cuts i: whenever the first piece pref[i] equals the second piece pref[j] - pref[i+1], we add that common value to a set left of acceptable sums.

Then we scan possible right cuts k. We compute the third piece s = pref[k] - pref[j+1]; if it equals the fourth piece pref[n] - pref[k+1] and s is already in left, then all four sums match and we return true.

Example: nums = [1,2,1,2,1,2,1]. For a middle cut, the left side can form a piece summing to 2, and a matching right piece also sums to 2, so a valid split exists and the answer is true.

Fixing j and doing two linear scans inside gives O(n²) overall, much faster than checking every (i, j, k) triple.

Time: O(n²) Space: O(n)