Ways to Split Array Into Three Subarrays - Video Solutions
LeetCode 1712. Ways to Split Array Into Three Subarrays | Visualization | Python
Ways to Split Array Into Three Subarrays - Video Solution
Watch 10 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,537 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
A split of an integer array is good if:
- The array is split into three non-empty contiguous subarrays - named
left,mid,rightrespectively from left to right. - The sum of the elements in
leftis less than or equal to the sum of the elements inmid, and the sum of the elements inmidis less than or equal to the sum of the elements inright.
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] <= 104
Approach Overview
Problem 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.
Complexity Analysis
| 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. |