Watch 9 video solutions for Ways to Split Array Into Three Subarrays, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by AH Tech has 7,446 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |