# LeetCode 548: Split Array with Equal Sum

## Problem Restatement

We are given an integer array `nums`.

We need to determine whether there exist indices:

```python
i, j, k
```

such that:

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

and the following four subarrays all have the same sum:

```text
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:

```python
True
```

if such a split exists, otherwise:

```python
False
```

The official statement defines the required equalities as:

$$
sum(0,i-1)=sum(i+1,j-1)=sum(j+1,k-1)=sum(k+1,n-1)
$$

with strict spacing between the indices. ([leetcode.ca](https://leetcode.ca/all/548.html?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Whether a valid split exists |
| Split count | Three indices `i, j, k` |
| Requirement | Four subarray sums must be equal |
| Split indices | Excluded from all sums |

Function shape:

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

## Examples

Consider:

```python
nums = [1, 2, 1, 2, 1, 2, 1]
```

Choose:

```python
i = 1
j = 3
k = 5
```

The four parts are:

| Part | Elements | Sum |
|---|---|---:|
| `nums[0:i]` | `[1]` | `1` |
| `nums[i+1:j]` | `[1]` | `1` |
| `nums[j+1:k]` | `[1]` | `1` |
| `nums[k+1:]` | `[1]` | `1` |

All sums are equal.

So the answer is:

```python
True
```

Another example:

```python
nums = [1, 2, 3, 4]
```

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

The answer is:

```python
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:

```python
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:

```python
prefix[t]
```

as the sum of:

```python
nums[0] through nums[t - 1]
```

Then:

$$
sum(left,right)=prefix[right+1]-prefix[left]
$$

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:

$$
sum(0,i-1)=sum(i+1,j-1)
$$

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:

$$
sum(j+1,k-1)=sum(k+1,n-1)
$$

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:

$$
sum(0,i-1)=prefix[i]
$$

Second region:

$$
sum(i+1,j-1)=prefix[j]-prefix[i+1]
$$

### Right side

Third region:

$$
sum(j+1,k-1)=prefix[k]-prefix[j+1]
$$

Fourth region:

$$
sum(k+1,n-1)=prefix[n]-prefix[k+1]
$$

## Correctness

The algorithm checks every valid middle split `j`.

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

$$
sum(0,i-1)=sum(i+1,j-1)
$$

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:

$$
sum(j+1,k-1)=sum(k+1,n-1)
$$

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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | For each `j`, we scan possible `i` and `k` |
| Space | `O(n)` | Prefix sums and temporary set |

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

## Implementation

```python
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:

```python
if n < 7:
    return False
```

We need enough space for:

```text
subarray, split, subarray, split, subarray, split, subarray
```

Then we build prefix sums:

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

Now subarray sums become constant-time operations.

The middle split `j` must leave room on both sides:

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

For each `j`, we collect valid left sums.

The left equality is:

```python
left_sum == middle_left_sum
```

meaning:

$$
sum(0,i-1)=sum(i+1,j-1)
$$

We store those sums in:

```python
seen
```

Then we scan valid `k` values on the right.

The right equality is:

```python
middle_right_sum == right_sum
```

meaning:

$$
sum(j+1,k-1)=sum(k+1,n-1)
$$

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

So we return:

```python
True
```

## Small Walkthrough

For:

```python
nums = [1, 2, 1, 2, 1, 2, 1]
```

Prefix sums:

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

Choose:

```python
j = 3
```

Try:

```python
i = 1
```

Then:

| Region | Sum |
|---|---:|
| `[1]` | `1` |
| `[1]` | `1` |

So:

```python
1
```

is added to `seen`.

Now try:

```python
k = 5
```

Right-side regions:

| Region | Sum |
|---|---:|
| `[1]` | `1` |
| `[1]` | `1` |

Since:

```python
1 in seen
```

all four regions have equal sum.

Return:

```python
True
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| Main sample | Standard valid split |
| Too few elements | Impossible case |
| All zeros | Many equal-sum splits |
| All ones | Valid equal partitions |
| Near-valid array | Confirms rejection when one region differs |