Ways to Split Array
Problem
Given an integer array nums, return the number of ways to split the array into two non-empty parts such that the sum of the left part is greater than or equal to the sum of the right part.
- 2 ≤ nums.length ≤ 10⁵
- −10⁵ ≤ nums[i] ≤ 10⁵
Example
nums = [10,4,-8,7]2The array can be split at indices 0, 1, or 2. Splitting at index 0 yields left = [10], right = [4, -8, 7], sums 10 and 3, left >= right, valid. Splitting at index 1 yields left = [10,4], right = [-8,7], sums 14 and -1, valid. Splitting at index 2 yields left = [10,4,-8], right = [7], sums 6 and 7, invalid. Thus, total valid splits = 2.
Approach
Straightforward Solution
A naive approach checks every split index by summing left and right parts separately, resulting in O(n^2) time, which is too slow for large inputs.
Core Observation
The sum of any subarray can be computed efficiently using prefix sums, allowing constant-time queries for left and right sums after a single O(n) preprocessing pass.
Path to Optimal
By precomputing prefix sums, the sum of the left part at index i is prefix[i], and the right part sum is total sum minus prefix[i]. This reduces each split check to O(1), enabling an O(n) solution by iterating through all possible split points once.
Optimal Approach
Compute prefix sums in O(n). Iterate through indices from 0 to n-2, for each index compute left sum as prefix[i] and right sum as prefix[-1] - prefix[i]. Increment count if left sum >= right sum. Return the count after processing all splits.
Time
O(n)
Prefix sums are computed in a single pass (O(n)), and the split checks iterate once through the array (O(n)), resulting in overall O(n) time.
Space
O(n)
An auxiliary prefix sum array of size n is used to store cumulative sums, which scales linearly with input size.
Pattern Spotlight
Prefix Sum (Range Sum Queries)
Precompute cumulative sums to transform repeated range sum queries from O(n) each to O(1), enabling linear-time solutions for problems involving subarray sums.
Solution
| 1 | class Solution: |
| 2 | def waysToSplitArray(self, nums: List[int]) -> int: |
| 3 | n = len(nums) |
| 4 | |
| 5 | prefix = [nums[0]] |
| 6 | for i in range(1, n): |
| 7 | prefix.append(nums[i] + prefix[-1]) |
| 8 | |
| 9 | ans = 0 |
| 10 | for i in range(n - 1): |
| 11 | left_section = prefix[i] |
| 12 | right_section = prefix[-1] - prefix[i] |
| 13 | if left_section >= right_section: |
| 14 | ans += 1 |
| 15 | |
| 16 | return ans |
Step-by-Step Solution
Compute Prefix Sum Array to Enable Fast Sum Queries
| 3 | n = len(nums) |
| 5 | prefix = [nums[0]] |
| 6 | for i in range(1, n): |
| 7 | prefix.append(nums[i] + prefix[-1]) |
Objective
To build a prefix sum array where each element at index i represents the sum of nums from index 0 to i.
Key Insight
Prefix sums convert repeated sum queries into constant-time operations by storing cumulative sums. This preprocessing step is essential to avoid recomputing sums for every split, which would be prohibitively expensive.
Interview Quick-Check
Core Logic
Prefix sum array stores cumulative sums, enabling O(1) retrieval of any subarray sum by subtraction.
Common Pitfalls & Bugs
Forgetting to initialize prefix with the first element or incorrectly indexing can cause off-by-one errors.
Iterate Over Possible Split Points and Count Valid Splits
| 9 | ans = 0 |
| 10 | for i in range(n - 1): |
| 11 | left_section = prefix[i] |
| 12 | right_section = prefix[-1] - prefix[i] |
| 13 | if left_section >= right_section: |
| 14 | ans += 1 |
Objective
To iterate through all valid split indices and count how many satisfy the condition left sum >= right sum.
Key Insight
Using the prefix sums, the left sum at index i is prefix[i], and the right sum is total sum minus prefix[i]. Comparing these sums in a single pass allows efficient counting of valid splits without redundant summations.
Interview Quick-Check
Core Logic
For each split index, compute left and right sums using prefix sums and increment count if left sum >= right sum.
State & Boundaries
Iterate only up to n-2 because both parts must be non-empty.
Common Pitfalls & Bugs
Incorrectly including the last index as a split point would create an empty right part, violating problem constraints.
Return the Total Count of Valid Splits
| 16 | return ans |
Objective
To return the accumulated count of valid splits after processing all possible split points.
Key Insight
Returning the count completes the solution, providing the number of ways to split the array according to the problem's condition.
Interview Quick-Check
Core Logic
Return the final count after iterating through all split points.
Line Analysis
This solution has 1 Critical line interviewers watch for.
if left_section >= right_section:Check if left section sum is greater than or equal to right section sum.
This condition directly implements the problem's requirement for a valid split.
prefix.append(nums[i] + prefix[-1])Append the sum of current nums element and last prefix sum to prefix array.
This line incrementally builds the prefix sums, enabling O(1) range sum queries later.
right_section = prefix[-1] - prefix[i]Calculate the sum of the right section by subtracting left sum from total sum.
Total sum is prefix[-1]; subtracting prefix[i] yields the sum of elements from i+1 to end, enabling O(1) right sum calculation.
prefix = [nums[0]]Initialize the prefix sum array with the first element of nums.
Starting prefix sums with nums[0] sets the base for cumulative sum calculation, ensuring correct accumulation from the start.
left_section = prefix[i]Calculate the sum of the left section using prefix sums.
Prefix[i] directly gives the sum of elements from index 0 to i, enabling constant-time sum retrieval.
ans += 1Increment the answer counter if the split is valid.
Counting valid splits accumulates the final result to be returned.
for i in range(n - 1):Iterate through all possible split indices from 0 to n-2.
Splitting at index i divides the array into two non-empty parts; iterating up to n-2 ensures the right part is non-empty.
for i in range(1, n):Begin loop from index 1 to build prefix sums.
Iterating from the second element allows accumulation of sums by adding current element to the last prefix sum.
return ansReturn the total count of valid splits.
This line outputs the final answer after all splits have been evaluated.
ans = 0Initialize the answer counter to zero.
This variable accumulates the count of valid splits satisfying the problem condition.
n = len(nums)Calculate the length of the input array nums.
Caching the length avoids repeated calls to len(nums) and clarifies the array size for subsequent loops.
Test Your Understanding
Why does using prefix sums reduce the time complexity from O(n^2) to O(n)?
Because prefix sums allow constant-time calculation of any subarray sum by subtracting two prefix values, eliminating the need to sum elements repeatedly for each split.
Related Problems
Prefix Sum pattern
Don't just read it. Drill it.
Reconstruct Ways to Split Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Ways to Split Array drill