Watch 10 video solutions for Number of Ways to Split Array, a medium level problem involving Array, Prefix Sum. This walkthrough by NeetCodeIO has 6,934 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums of length n.
nums contains a valid split at index i if the following are true:
i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.i. That is, 0 <= i < n - 1.Return the number of valid splits in nums.
Example 1:
Input: nums = [10,4,-8,7] Output: 2 Explanation: There are three ways of splitting nums into two non-empty parts: - Split nums at index 0. Then, the first part is [10], and its sum is 10. The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, i = 0 is a valid split. - Split nums at index 1. Then, the first part is [10,4], and its sum is 14. The second part is [-8,7], and its sum is -1. Since 14 >= -1, i = 1 is a valid split. - Split nums at index 2. Then, the first part is [10,4,-8], and its sum is 6. The second part is [7], and its sum is 7. Since 6 < 7, i = 2 is not a valid split. Thus, the number of valid splits in nums is 2.
Example 2:
Input: nums = [2,3,1,0] Output: 2 Explanation: There are two valid splits in nums: - Split nums at index 1. Then, the first part is [2,3], and its sum is 5. The second part is [1,0], and its sum is 1. Since 5 >= 1, i = 1 is a valid split. - Split nums at index 2. Then, the first part is [2,3,1], and its sum is 6. The second part is [0], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.
Constraints:
2 <= nums.length <= 105-105 <= nums[i] <= 105Problem Overview: You are given an integer array nums. A split index divides the array into a left subarray [0..i] and a right subarray [i+1..n-1]. A split is valid when the sum of the left part is greater than or equal to the sum of the right part. The task is to count how many such split positions exist.
Approach 1: Two-Pass Prefix Array (O(n) time, O(n) space)
This approach builds a prefix sum array where prefix[i] stores the sum of elements from index 0 to i. First iterate through the array to compute prefix sums. Then iterate again and evaluate each possible split. For a split at i, the left sum is prefix[i] and the right sum is prefix[n-1] - prefix[i]. If prefix[i] >= prefix[n-1] - prefix[i], the split is valid. This approach is straightforward and easy to reason about because both subarray sums are retrieved in constant time. It’s a good starting point when working with prefix sum problems on arrays.
Approach 2: Running Prefix Sum (O(n) time, O(1) space)
The prefix array can be eliminated by computing the total sum first. Iterate through the array once to get totalSum. Then iterate again while maintaining a running prefix sum leftSum. At each index i, the right subarray sum becomes totalSum - leftSum. If leftSum >= totalSum - leftSum, the split is valid. This works because every valid split simply compares the accumulated left sum with the remaining sum of the array. The algorithm only tracks a few variables, so it reduces space usage to constant while keeping the same linear runtime.
The key insight is that every split can be evaluated using prefix sums. Instead of recomputing sums for each partition (which would lead to O(n²) time), prefix accumulation lets you evaluate each split in constant time while scanning the array once.
Recommended for interviews: The running prefix sum solution is the expected answer. Interviewers want to see that you recognize this as a prefix sum pattern and avoid repeated summation. Mentioning the prefix array approach first shows understanding of the concept, while optimizing it to O(1) space demonstrates stronger problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Prefix Array | O(n) | O(n) | Good for learning prefix sums or when explicit prefix storage is useful for multiple queries |
| Running Prefix Sum | O(n) | O(1) | Optimal approach for interviews and production code with minimal memory usage |