LeetCode 548: Split Array with Equal Sum

Problem Restatement

We are given an integer array nums.

We need to determine whether there exist indices:

i, j, k

such that:

0 < i
i + 1 < j
j + 1 < k
k < n - 1

and the following four subarrays all have the same sum:

nums[0 : i]
nums[i + 1 : j]
nums[j + 1 : k]
nums[k + 1 : n]

The split indices themselves are excluded from all subarrays.

We return:

True

if such a split exists, otherwise:

False

The official statement defines the required equalities as:

with strict spacing between the indices. (leetcode.ca)

Input and Output

Function shape:

def splitArray(nums: list[int]) -> bool:
    ...

Examples

Consider:

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

Choose:

i = 1
j = 3
k = 5

The four parts are:

All sums are equal.

So the answer is:

True

Another example:

nums = [1, 2, 3, 4]

There are not enough elements to create four non-empty regions satisfying the spacing constraints.

The answer is:

False

First Thought: Try Every Triple

A direct solution is:

1. Try every valid i.
2. Try every valid j.
3. Try every valid k.
4. Compute the four sums.
5. Check whether they are equal.

This works, but it is too slow.

There are:

O(n^3)

possible triples.

If we also compute sums directly from subarrays, the complexity becomes even worse.

We need prefix sums and a smarter search.

Key Insight

Prefix sums let us compute any subarray sum in constant time.

Define:

prefix[t]

as the sum of:

nums[0] through nums[t - 1]

Then:

The important observation is that we can fix the middle split j.

Then:

• The left side involves choosing i
• The right side involves choosing k

For the left side, we want:

If this equality holds, then that shared sum becomes a candidate target.

We store all such candidate sums in a set.

Then on the right side we search for k satisfying:

If the shared right-side sum also appears in the left-side set, then all four parts have the same sum.

Algorithm

1. Compute prefix sums.
2. Iterate over possible middle split j.
3. For each j:
   1. Create an empty set seen.
   2. Try all valid i values on the left side.
   3. If the two left sums are equal, add that sum to seen.
4. Then try all valid k values on the right side.
5. If the two right sums are equal and that sum exists in seen, return True.
6. If no split works, return False.

Prefix Sum Formulas

Using prefix sums:

Left side

First region:

Second region:

Right side

Third region:

Fourth region:

Correctness

The algorithm checks every valid middle split j.

For each such j, the algorithm examines every valid left split i. Whenever:

holds, the common value is stored in seen.

Therefore, after the left scan, seen contains exactly the sums that can form two equal left-side regions for the current j.

Next, the algorithm examines every valid right split k. Whenever:

holds, the common right-side sum is computed.

If that sum also exists in seen, then:

• the first and second regions are equal,
• the third and fourth regions are equal,
• and the shared value matches between left and right sides.

So all four regions have equal sum, and the algorithm correctly returns True.

If the algorithm finishes without returning True, then no valid (i, j, k) satisfies all four equalities, because every valid split combination was checked through the fixed-middle strategy.

Therefore, the algorithm is correct.

Complexity

Let n = len(nums).

This is much faster than brute force O(n^3) search.

Implementation

class Solution:
    def splitArray(self, nums: list[int]) -> bool:
        n = len(nums)

        if n < 7:
            return False

        prefix = [0] * (n + 1)

        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        for j in range(3, n - 3):
            seen = set()

            for i in range(1, j - 1):
                left_sum = prefix[i]
                middle_left_sum = prefix[j] - prefix[i + 1]

                if left_sum == middle_left_sum:
                    seen.add(left_sum)

            for k in range(j + 2, n - 1):
                middle_right_sum = prefix[k] - prefix[j + 1]
                right_sum = prefix[n] - prefix[k + 1]

                if middle_right_sum == right_sum:
                    if middle_right_sum in seen:
                        return True

        return False

Code Explanation

We first reject impossible small arrays:

if n < 7:
    return False

We need enough space for:

subarray, split, subarray, split, subarray, split, subarray

Then we build prefix sums:

prefix[i + 1] = prefix[i] + nums[i]

Now subarray sums become constant-time operations.

The middle split j must leave room on both sides:

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

For each j, we collect valid left sums.

The left equality is:

left_sum == middle_left_sum

meaning:

We store those sums in:

seen

Then we scan valid k values on the right.

The right equality is:

middle_right_sum == right_sum

meaning:

If this shared right-side sum exists in seen, then all four parts have equal sum.

So we return:

True

Small Walkthrough

For:

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

Prefix sums:

[0, 1, 3, 4, 6, 7, 9, 10]

Choose:

j = 3

Try:

i = 1

Then:

So:

1

is added to seen.

Now try:

k = 5

Right-side regions:

Since:

1 in seen

all four regions have equal sum.

Return:

True

Testing

def run_tests():
    s = Solution()

    assert s.splitArray([1, 2, 1, 2, 1, 2, 1]) is True

    assert s.splitArray([1, 2, 3, 4]) is False

    assert s.splitArray([0, 0, 0, 0, 0, 0, 0]) is True

    assert s.splitArray([1, 1, 1, 1, 1, 1, 1]) is True

    assert s.splitArray([1, 2, 1, 2, 1, 2, 2]) is False

    print("all tests passed")

run_tests()