A split of an integer array is good if:
left, mid, right respectively from left to right.left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,1,1] Output: 1 Explanation: The only good way to split nums is [1] [1] [1].
Example 2:
Input: nums = [1,2,2,2,5,0] Output: 3 Explanation: There are three good ways of splitting nums: [1] [2] [2,2,5,0] [1] [2,2] [2,5,0] [1,2] [2,2] [5,0]
Example 3:
Input: nums = [3,2,1] Output: 0 Explanation: There is no good way to split nums.
Constraints:
3 <= nums.length <= 1050 <= nums[i] <= 104Problem Overview: Given an integer array, split it into three non-empty contiguous subarrays left, mid, and right. The split is valid when sum(left) ≤ sum(mid) ≤ sum(right). The goal is to count how many index pairs (i, j) create such a split.
Approach 1: Prefix Sum and Two Pointers (O(n) time, O(n) space)
First compute a prefix sum array so any subarray sum can be calculated in O(1). Fix the first split index i, which determines the left subarray. Then move two pointers j and k to represent the valid range of the second split that forms the mid subarray. Increase j until sum(mid) ≥ sum(left), and increase k while sum(mid) ≤ sum(right). Because both pointers only move forward across the array, the total work stays linear. This technique combines array traversal with two pointers to efficiently count all valid positions.
Approach 2: Prefix Sum and Binary Search (O(n log n) time, O(n) space)
Use the prefix sum array to convert the constraints into numeric bounds. For each first split index i, the second split index j must satisfy two inequalities: prefix[j] - prefix[i] ≥ prefix[i] and prefix[j] - prefix[i] ≤ total - prefix[j]. Rearranging these conditions gives a valid range of prefix values for j. Because the prefix array is non-decreasing, you can use binary search to find the first and last valid indices. The number of valid splits for that i equals the size of this range. This approach is straightforward to implement and easier to reason about than pointer movement.
Recommended for interviews: Prefix Sum with Two Pointers is the expected optimal approach. It reduces the search space from O(n log n) to O(n) by exploiting the monotonic movement of valid split boundaries. Showing the binary search approach first demonstrates understanding of prefix sums and range constraints, but implementing the linear two-pointer solution shows stronger algorithmic optimization skills.
In this method, we utilize a prefix sum array to speed up the calculation of subarray sums. Using two pointers, we attempt to find ranges for the middle subarray that satisfy the given constraints for each choice of the first split point.
We create a prefix sum array where prefix[i] stores the sum of numbers from start to i-1. We loop over possible positions for the first cut and then use two pointers.
The loop updates the count for valid splits by calculating k - j, and then we apply the modulo operation.
Time Complexity: O(n), where n is the size of the array. Each step in the algorithm processes elements in linear time.
Space Complexity: O(n), for storing the prefix sum array.
This method uses a prefix sum array to manage efficiency and applies binary search to quickly determine the bounds needed for a proper split, checking for valid middle subarrays using binary search for faster lookup of boundaries.
This C solution combines prefix sums with binary searches via custom lower and upper bound functions to swiftly determine the range of indices that work for a valid middle subarray, both optimized with binary search.
Time Complexity: O(n log n), due to binary searches.
Space Complexity: O(n), for prefix sums.
First, we preprocess the prefix sum array s of the array nums, where s[i] represents the sum of the first i+1 elements of the array nums.
Since all elements of the array nums are non-negative integers, the prefix sum array s is a monotonically increasing array.
We enumerate the index i that the left subarray can reach in the range [0,..n-2), and then use the monotonically increasing characteristic of the prefix sum array to find the reasonable range of the mid subarray split by binary search, denoted as [j, k), and accumulate the number of schemes k-j.
In the binary search details, the subarray split must satisfy s[j] geq s[i] and s[n - 1] - s[k] geq s[k] - s[i]. That is, s[j] geq s[i] and s[k] leq \frac{s[n - 1] + s[i]}{2}.
Finally, return the number of schemes modulo 10^9+7.
The time complexity is O(n times log n), where n is the length of the array nums.
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Prefix Sum and Two Pointers | Time Complexity: O(n), where n is the size of the array. Each step in the algorithm processes elements in linear time. |
| Prefix Sum and Binary Search | Time Complexity: O(n log n), due to binary searches. |
| Prefix Sum + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum + Two Pointers | O(n) | O(n) | Best overall approach. Linear scan with monotonic pointers for maximum efficiency. |
| Prefix Sum + Binary Search | O(n log n) | O(n) | Simpler reasoning. Useful when pointer window logic feels tricky. |
LeetCode 1712. Ways to Split Array Into Three Subarrays | Visualization | Python • AH Tech • 7,446 views views
Watch 8 more video solutions →Practice Ways to Split Array Into Three Subarrays with our built-in code editor and test cases.
Practice on FleetCode