LeetCode 548 - Split Array with Equal Sum

The problem asks us to determine whether an integer array nums can be split into four non-empty subarrays with equal sums by selecting three indices i, j, and k that satisfy strict ordering constraints: 0 < i, i + 1 < j, j + 1 < k < n - 1.

leetcodehardarrayhash-tableprefix-sum

LeetCode Problem 548

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine whether an integer array nums can be split into four non-empty subarrays with equal sums by selecting three indices i, j, and k that satisfy strict ordering constraints: 0 < i, i + 1 < j, j + 1 < k < n - 1. These indices define the boundaries of four contiguous subarrays: the first from index 0 to i-1, the second from i+1 to j-1, the third from j+1 to k-1, and the fourth from k+1 to n-1.

The input is a single integer array nums with up to 2000 elements, each element potentially ranging from -10^6 to 10^6. The output is a boolean indicating whether such a split exists.

Important edge cases include very small arrays where no split is possible, arrays with all equal elements where multiple splits may exist, and arrays with negative values which could break naive sum comparisons. The problem guarantees that the array has at least one element, but the strict index constraints mean that the array must be at least of length 7 to allow a valid (i, j, k) triplet.

Approaches

A brute-force solution would involve iterating over all possible triplets (i, j, k) that satisfy the constraints and checking if the sums of the four subarrays are equal. This guarantees correctness because it evaluates every valid combination. However, computing subarray sums repeatedly without precomputation would require O(n^3) time and would be infeasible for n = 2000.

The key insight for optimization is the use of prefix sums to compute subarray sums in constant time and a hash set to store potential sum matches. By fixing the middle index j and checking the left and right partitions with prefix sums, we can significantly reduce the number of operations. Specifically, for each j, we examine all valid i to the left and k to the right, and track which sums have been seen using a set. This reduces the complexity from O(n^3) to roughly O(n^2) while using additional space for prefix sums.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Check every possible (i, j, k) triplet with nested loops, compute sums repeatedly
Optimal O(n^2) O(n) Use prefix sums for constant-time sum calculation and a hash set to track valid splits

Algorithm Walkthrough

  1. Compute a prefix sum array prefix such that prefix[x] equals the sum of all elements from nums[0] to nums[x]. This allows O(1) calculation of any subarray sum via prefix[r] - prefix[l-1] if l > 0, otherwise prefix[r].
  2. Iterate over all possible middle indices j from 3 to n-4. This ensures there is enough room on both sides to select valid i and k.
  3. For each j, maintain a hash set seen_sums for sums of potential left partitions. Iterate over i from 1 to j-2 and check if the sum from 0 to i-1 equals the sum from i+1 to j-1. If it does, add that sum to seen_sums.
  4. Iterate over potential k from j+2 to n-2. Compute the sums of the right partitions from j+1 to k-1 and k+1 to n-1. If these sums match a sum in seen_sums, then a valid split exists and return true.
  5. If no valid (i, j, k) triplet satisfies the condition after examining all j, return false.

Why it works: By fixing j and examining all i to the left and k to the right using prefix sums, we efficiently check every valid combination of left and right subarrays without repeated summation. The hash set ensures that we only consider sums that can be matched on both sides, maintaining correctness.

Python Solution

from typing import List

class Solution:
    def splitArray(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 7:
            return False
        
        prefix = [0] * n
        prefix[0] = nums[0]
        for i in range(1, n):
            prefix[i] = prefix[i - 1] + nums[i]
        
        for j in range(3, n - 3):
            seen_sums = set()
            for i in range(1, j - 1):
                if prefix[i - 1] == prefix[j - 1] - prefix[i]:
                    seen_sums.add(prefix[i - 1])
            
            for k in range(j + 2, n - 1):
                right_sum = prefix[n - 1] - prefix[k]
                middle_right_sum = prefix[k - 1] - prefix[j]
                if middle_right_sum == right_sum and middle_right_sum in seen_sums:
                    return True
        
        return False

The implementation first calculates the prefix sum array to allow O(1) subarray sum queries. It then iterates over possible middle indices j, collecting left sums into a set and checking matching sums on the right. By using the prefix sum array and set, we reduce repeated calculations and efficiently determine whether a valid split exists.

Go Solution

func splitArray(nums []int) bool {
    n := len(nums)
    if n < 7 {
        return false
    }
    
    prefix := make([]int, n)
    prefix[0] = nums[0]
    for i := 1; i < n; i++ {
        prefix[i] = prefix[i-1] + nums[i]
    }
    
    for j := 3; j < n-3; j++ {
        seenSums := make(map[int]struct{})
        for i := 1; i < j-1; i++ {
            if prefix[i-1] == prefix[j-1]-prefix[i] {
                seenSums[prefix[i-1]] = struct{}{}
            }
        }
        
        for k := j + 2; k < n-1; k++ {
            rightSum := prefix[n-1] - prefix[k]
            middleRightSum := prefix[k-1] - prefix[j]
            if middleRightSum == rightSum {
                if _, ok := seenSums[middleRightSum]; ok {
                    return true
                }
            }
        }
    }
    
    return false
}

In Go, we use a map with empty struct values to efficiently track seen sums. The logic mirrors the Python version: compute prefix sums, iterate over j, track left sums in a set, and check for matching right sums.

Worked Examples

Example 1: nums = [1,2,1,2,1,2,1]

j i loop seen_sums k loop check
3 i=1 → prefix[0] = 1 added k=5 → middleRightSum = 1, rightSum = 1 → match found

Result: true

Example 2: nums = [1,2,1,2,1,2,1,2]

No combination of (i, j, k) produces equal sums across all four subarrays, so the result is false.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Outer loop over j is O(n), inner loops over i and k are O(n) in total. Prefix sums allow constant-time sum calculation.
Space O(n) Prefix sum array of size n, plus a hash set whose size is at most O(n) for seen sums.

The use of prefix sums and hash set reduces repeated subarray sum computations, making O(n^2) feasible for n up to 2000.

Test Cases

# Basic example from problem statement
assert Solution().splitArray([1,2,1,2,1,2,1]) == True  # split exists
assert Solution().splitArray([1,2,1,2,1,2,1,2]) == False  # no split

# Minimum length arrays
assert Solution().splitArray([1,1,1,1,1,1,1]) == True  # all ones
assert Solution().splitArray([1,1,1,1,1,1]) == False  # length < 7

# Negative numbers
assert Solution().splitArray([-1,1,-1,1,-1,1,-1]) == True  # alternating negative/positive

# All zeros
assert Solution().splitArray([0,0,0,0,0,0,0]) == True  # zero sum subarrays

# Random large values
assert Solution().splitArray([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]) == False
Test Why
[1,2,1,2,1,2,1] Basic valid split
[1