Skip to main content
Talentd

Split Array with Equal Sum - Solution & Explanation

HardPremiumFree on FleetCodeArrayHash TablePrefix Sum5 min readAsked at: Alibaba
Practice this problem

Problem Statement

Given an integer array nums of length n, return true if there is a triplet (i, j, k) which satisfies the following conditions:

  • 0 < i, i + 1 < j, j + 1 < k < n - 1
  • The sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) is equal.
A subarray (l, r) represents a slice of the original array starting from the element indexed l to the element indexed r.

 

Example 1:

Input: nums = [1,2,1,2,1,2,1]
Output: true
Explanation:
i = 1, j = 3, k = 5. 
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

Example 2:

Input: nums = [1,2,1,2,1,2,1,2]
Output: false

 

Constraints:

  • n == nums.length
  • 1 <= n <= 2000
  • -106 <= nums[i] <= 106

Approach Overview

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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Prefix SumO(n^3)O(n)Understanding the structure of valid splits or validating correctness for small inputs
Prefix Sum + Hash SetO(n^2)O(n)General case and expected interview solution

Video Solution

Leetcode 548 Split Array with Equal Sum • Ren Zhang • 3,170 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Split Array with Equal Sum easy or hard?
Split Array with Equal Sum is classified as a hard problem. The challenge comes from managing multiple split points while ensuring four segments have identical sums, which requires combining prefix sums with hash-based pruning.
Split Array with Equal Sum Python/Java solution
Implement the optimized approach by first building a prefix sum array. Iterate over possible middle indices j, collect valid left-side sums in a set, and then check right-side splits for matches. The same logic works in Python, Java, C++, and Go with O(n^2) time and O(n) space.
How to solve Split Array with Equal Sum in O(n)?
A true O(n) solution is not known for this problem because three ordered split points must be evaluated. The commonly accepted optimal approach uses prefix sums and a hash set to reduce the complexity to O(n^2) while keeping subarray sum queries constant time.
What is the best approach for Split Array with Equal Sum?
The most effective solution uses prefix sums with a hash set. Fix the middle index j, store valid left-side split sums using indices i, and then scan the right side for indices k that produce the same sum. This reduces the search from O(n^3) to O(n^2) while keeping space complexity at O(n).
Is Split Array with Equal Sum asked at Google/Amazon/Meta?
This problem reflects the type of array partitioning and prefix-sum reasoning commonly seen in interviews at large tech companies such as Google, Amazon, and Meta. Variants of equal partition or subarray sum problems appear frequently in coding interviews.
What data structure is used in Split Array with Equal Sum?
The core structures are a prefix sum array and a hash set. Prefix sums allow constant-time subarray sum calculations, while the hash set stores valid left-side sums so matching right-side splits can be checked quickly.
What is the time complexity of Split Array with Equal Sum?
The optimized solution runs in O(n^2) time. For each middle index j, the algorithm scans the left portion once and the right portion once, using a hash set for constant-time lookups. Space complexity is O(n) due to the prefix sum array and temporary set.

Ready to solve this problem?

Practice Split Array with Equal Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Fair Distribution of Cookies

Next

Number of Ways to Split a String