Number of Ways to Split Array
Description
Given an integer array nums, find the number of ways to split the array into two parts so that the first section has a sum greater than or equal to the sum of the second section. The second section should have at least one number.
Example 1:
Input: nums = [10, 4, -8, 7]
Output: 2
Explanation: There are three ways to split nums:
- Split at index 0: [10] and [4, -8, 7]. Sums are 10 and 3. 10 >= 3, valid.
- Split at index 1: [10, 4] and [-8, 7]. Sums are 14 and -1. 14 >= -1, valid.
- Split at index 2: [10, 4, -8] and [7]. Sums are 6 and 7. 6 >= 7 is false, invalid.
So there are 2 valid splits.
Example 2:
Input: nums = [2, 3, 1, 0]
Output: 2
Explanation:
- Split at index 0: [2] and [3, 1, 0]. Sums are 2 and 4. 2 >= 4 is false.
- Split at index 1: [2, 3] and [1, 0]. Sums are 5 and 1. 5 >= 1, valid.
- Split at index 2: [2, 3, 1] and [0]. Sums are 6 and 0. 6 >= 0, valid.
So there are 2 valid splits.
Constraints
2 <= nums.length <= 10^5-10^5 <= nums[i] <= 10^5
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show Hints
- Pattern
- Prefix sum
- Approach
- For each split index i (0 to n-2), check if left_sum >= right_sum. Use: right_sum = total - left_sum
- Complexity
- Compute total sum first, then iterate once tracking left sum
Solutions
Show PY Solution
def solution(nums):
count = 0
total = sum(nums)
left_section = 0
for i in range(len(nums) - 1):
left_section += nums[i]
right_section = total - left_section
if left_section >= right_section:
count += 1
return count