Problem Description

Given an integer array nums of length at least 7, split it into four non-overlapping subarrays by selecting three indices i, j, and k such that:

• 0 < i, i + 1 < j, j + 1 < k < nums.length - 1
• The sum of the subarrays are equal, where:
  • First subarray: nums[0] ... nums[i-1]
  • Second subarray: nums[i+1] ... nums[j-1]
  • Third subarray: nums[j+1] ... nums[k-1]
  • Fourth subarray: nums[k+1] ... nums[nums.length-1]

Find if there exists at least one set of such indices where all four subarrays have the same sum. Each element must only belong to one subarray, and you cannot reuse elements.

Return true if such a split exists, otherwise return false.

Thought Process

At first glance, this problem seems to require checking all possible combinations of indices i, j, and k to see if the four resulting subarrays have equal sums. This brute-force approach would be extremely slow, as the number of possible combinations grows rapidly with the size of the array.

To optimize, we realize that if we precompute the prefix sums of the array, we can quickly calculate the sum of any subarray in constant time. We also notice that for a fixed j, we can efficiently search for valid i and k that satisfy the sum condition. By leveraging hash sets to store possible sums for different splits, we can avoid redundant calculations and check for matches efficiently.

This shift from brute-force checking to using prefix sums and hash sets is key to making the solution efficient.

Solution Approach

Let's break down the optimized algorithm step by step:

1. Compute Prefix Sums:
   • Create an array prefix where prefix[x] is the sum of nums[0] ... nums[x-1].
   • This allows us to compute the sum of any subarray nums[a]...nums[b] as prefix[b+1] - prefix[a] in constant time.
2. Iterate Over Possible Middle Cuts:
   • We fix j (the middle cut) from 3 to n-4 (to ensure room for the other cuts).
3. Find All Valid Left Splits:
   • For each j, iterate i from 1 to j-2 (so subarrays are non-empty).
   • Calculate the sums of the first and second subarrays.
   • If they are equal, add the sum to a set sums.
4. Find All Valid Right Splits:
   • For the same j, iterate k from j+2 to n-2.
   • Calculate the sums of the third and fourth subarrays.
   • If they are equal and the sum exists in sums, return true (a valid split exists).
5. If No Valid Split is Found:
   • After checking all possible j, return false.

We use a hash set to quickly check if a sum found in the right split matches a sum found in the left split for the same j.

Example Walkthrough

Consider nums = [1, 2, 1, 2, 1, 2, 1].

1. Compute Prefix Sums:
   • prefix = [0, 1, 3, 4, 6, 7, 9, 10]
2. Try All Possible j:
   • Let’s pick j = 3 (so i can be 1, k can be 5).
3. Left Split:
   • For i = 1:
     • First subarray: nums[0] sum = 1
     • Second subarray: nums[2] sum = 1
     • Both sums are equal, so add 1 to sums.
4. Right Split:
   • For k = 5:
     • Third subarray: nums[4] sum = 1
     • Fourth subarray: nums[6] sum = 1
     • Both sums are equal, and 1 is in sums, so return true.

The process identifies the valid split: [1], [1], [1], [1] (with indices i=1, j=3, k=5).

Time and Space Complexity

• Brute-force approach:
  • Time: O(n³) because we would check all possible combinations of i, j, k.
  • Space: O(1) (ignoring input size).
• Optimized approach:
  • Time: O(n²) — For each possible j, we do two linear scans (one for i, one for k).
  • Space: O(n) — For the prefix sum array and temporary hash sets.

The optimization is significant: from checking all triples to a manageable double loop with fast lookups.

Summary

The key insight is to use prefix sums for fast subarray sum calculation and hash sets to efficiently check for matching subarray sums. By iterating over possible middle cuts and checking possible left and right splits, we avoid redundant checks and achieve a much faster solution than brute-force. This approach elegantly balances clarity and efficiency, making the problem solvable even for larger arrays.

Code Implementation

class Solution:
    def splitArray(self, nums):
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
        # Try all possible j
        for j in range(3, n - 3):
            sums = set()
            # Left side: try all i
            for i in range(1, j - 1):
                sum1 = prefix[i]
                sum2 = prefix[j] - prefix[i+1]
                if sum1 == sum2:
                    sums.add(sum1)
            # Right side: try all k
            for k in range(j + 2, n - 1):
                sum3 = prefix[k] - prefix[j+1]
                sum4 = prefix[n] - prefix[k+1]
                if sum3 == sum4 and sum3 in sums:
                    return True
        return False
      

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + nums[i];
        for (int j = 3; j <= n - 4; ++j) {
            unordered_set<int> sums;
            for (int i = 1; i <= j - 2; ++i) {
                int sum1 = prefix[i];
                int sum2 = prefix[j] - prefix[i + 1];
                if (sum1 == sum2)
                    sums.insert(sum1);
            }
            for (int k = j + 2; k <= n - 2; ++k) {
                int sum3 = prefix[k] - prefix[j + 1];
                int sum4 = prefix[n] - prefix[k + 1];
                if (sum3 == sum4 && sums.count(sum3))
                    return true;
            }
        }
        return false;
    }
};
      

class Solution {
    public boolean splitArray(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + nums[i];
        for (int j = 3; j <= n - 4; ++j) {
            HashSet<Integer> sums = new HashSet<>();
            for (int i = 1; i <= j - 2; ++i) {
                int sum1 = prefix[i];
                int sum2 = prefix[j] - prefix[i + 1];
                if (sum1 == sum2)
                    sums.add(sum1);
            }
            for (int k = j + 2; k <= n - 2; ++k) {
                int sum3 = prefix[k] - prefix[j + 1];
                int sum4 = prefix[n] - prefix[k + 1];
                if (sum3 == sum4 && sums.contains(sum3))
                    return true;
            }
        }
        return false;
    }
}
      

var splitArray = function(nums) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i)
        prefix[i + 1] = prefix[i] + nums[i];
    for (let j = 3; j <= n - 4; ++j) {
        const sums = new Set();
        for (let i = 1; i <= j - 2; ++i) {
            const sum1 = prefix[i];
            const sum2 = prefix[j] - prefix[i + 1];
            if (sum1 === sum2)
                sums.add(sum1);
        }
        for (let k = j + 2; k <= n - 2; ++k) {
            const sum3 = prefix[k] - prefix[j + 1];
            const sum4 = prefix[n] - prefix[k + 1];
            if (sum3 === sum4 && sums.has(sum3))
                return true;
        }
    }
    return false;
};