Split Array with Equal Sum solution and explanation
4 more videos on this problem
Leetcode 548 Split Array with Equal SumRen Zhang · 14:57 · 3K views
548. Split Array with Equal Sum | English | MediumSimple Code - 단순코드 · 13:10 · 654 views
548 Split Array with Equal SumJW Leetcode · 22:58 · 539 views
548. Split Array with Equal Sum | Korean | MediumSimple Code - 단순코드 · 13:27 · 51 views
LeetCode 548: Split Array with Equal SumAlitaCode · 28:51 · 6 views
The problem
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.
(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.length1 <= 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
class Solution:
def splitArray(self, nums: List[int]) -> bool:
n = len(nums)
s = [0] * (n + 1)
for i, v in enumerate(nums):
s[i + 1] = s[i] + v
for j in range(3, n - 3):
seen = set()
for i in range(1, j - 1):
if s[i] == s[j] - s[i + 1]:
seen.add(s[i])
for k in range(j + 2, n - 1):
if s[n] - s[k + 1] == s[k] - s[j + 1] and s[n] - s[k + 1] in seen:
return True
return Falseclass Solution {
public boolean splitArray(int[] nums) {
int n = nums.length;
int[] s = new int[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
for (int j = 3; j < n - 3; ++j) {
Set<Integer> seen = new HashSet<>();
for (int i = 1; i < j - 1; ++i) {
if (s[i] == s[j] - s[i + 1]) {
seen.add(s[i]);
}
}
for (int k = j + 2; k < n - 1; ++k) {
if (s[n] - s[k + 1] == s[k] - s[j + 1] && seen.contains(s[n] - s[k + 1])) {
return true;
}
}
}
return false;
}
}class Solution {
public:
bool splitArray(vector<int>& nums) {
int n = nums.size();
vector<int> s(n + 1);
for (int i = 0; i < n; ++i) s[i + 1] = s[i] + nums[i];
for (int j = 3; j < n - 3; ++j) {
unordered_set<int> seen;
for (int i = 1; i < j - 1; ++i)
if (s[i] == s[j] - s[i + 1])
seen.insert(s[i]);
for (int k = j + 2; k < n - 1; ++k)
if (s[n] - s[k + 1] == s[k] - s[j + 1] && seen.count(s[n] - s[k + 1]))
return true;
}
return false;
}
};func splitArray(nums []int) bool {
n := len(nums)
s := make([]int, n+1)
for i, v := range nums {
s[i+1] = s[i] + v
}
for j := 3; j < n-3; j++ {
seen := map[int]bool{}
for i := 1; i < j-1; i++ {
if s[i] == s[j]-s[i+1] {
seen[s[i]] = true
}
}
for k := j + 2; k < n-1; k++ {
if s[n]-s[k+1] == s[k]-s[j+1] && seen[s[n]-s[k+1]] {
return true
}
}
}
return false
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Prefix Sum | O(n^3) | O(n) | Understanding the structure of valid splits or validating correctness for small inputs |
| Prefix Sum + Hash Set | O(n^2) | O(n) | General case and expected interview solution |
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.