Split Array with Equal Sum - Solution & Explanation

Problem Overview: You receive an integer array and must determine whether it can be split using three indices i, j, and k so that four non-overlapping subarrays have the same sum. The indices must satisfy 0 < i < j < k < n-1, and the sums of the segments [0..i-1], [i+1..j-1], [j+1..k-1], and [k+1..n-1] must be equal.

Approach 1: Brute Force Enumeration (O(n^3) time, O(n) space)

Start by precomputing a prefix sum array so any subarray sum can be calculated in constant time. Then enumerate all valid combinations of split points i, j, and k. For every triple, compute the four segment sums using prefix differences and check whether they match. The prefix array reduces repeated summation, but the triple nested loops still produce O(n^3) time complexity. Space complexity remains O(n) for the prefix sums. This approach is straightforward and helps verify the constraints, but it is too slow for larger inputs.

Approach 2: Prefix Sum + Hash Set Optimization (O(n^2) time, O(n) space)

The key observation is that the middle index j separates the array into left and right regions that can be processed independently. Compute prefix sums first. For each possible j, scan the left side to find indices i where sum(0,i-1) == sum(i+1,j-1). Store these valid sums in a hash set using a hash table for constant-time lookup. Next, scan the right side for indices k where sum(j+1,k-1) == sum(k+1,n-1). If this value exists in the set of left-side sums, the array can be split correctly. The hash lookup eliminates one nested loop, reducing the complexity to O(n^2) while using O(n) extra space.

This method relies heavily on fast range-sum queries from the prefix sum array and constant-time membership checks from the hash table. Iterating over possible middle indices ensures every valid partition structure is evaluated without recomputing sums repeatedly.

Recommended for interviews: The prefix sum + hash set approach is what interviewers expect. It demonstrates that you recognize repeated subarray sum calculations and eliminate them using prefix sums, then reduce the search space with hash-based lookups. Starting with the brute force explanation shows you understand the structure of the problem, while arriving at the O(n^2) solution demonstrates strong optimization and algorithm design skills.