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.
This approach involves maintaining a running sum of elements as we iterate through the array and comparing the current left sum with the required condition for the split to be valid.
The function first calculates the total sum of the array. It then iterates over the array, updating the left sum and checking if the condition for a valid split is met. It counts and returns the number of valid splits.
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) as we are using a constant amount of extra space.
This approach consists of a first pass to calculate the total sum and a second pass to check the validity of each possible split by comparing the prefix sum with the remaining sum.
This approach uses two separate loops: one to calculate total sum first, and then a second loop to check conditions for valid splits based on prefix sum calculations.
Time Complexity: O(n)
Space Complexity: O(1)
First, we calculate the total sum s of the array nums. Then, we traverse the first n-1 elements of the array nums, using the variable t to record the prefix sum. If t geq s - t, we increment the answer by one.
After the traversal, we return the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prefix Sum Approach | Time Complexity: O(n) where n is the length of the array. |
| Two-Pass Array Approach | Time Complexity: O(n) |
| Prefix Sum | — |
| 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 |
Number of Ways to Split Array - Leetcode 2270 - Python • NeetCodeIO • 6,934 views views
Watch 9 more video solutions →Practice Number of Ways to Split Array with our built-in code editor and test cases.
Practice on FleetCode