You are given a 0-indexed integer array nums of length n. A split at index i is valid if the sum of the first i + 1 elements is greater than or equal to the sum of the remaining elements. Return the number of valid splits.

Examples

Example 1:

Input: nums = [10,4,-8,7]
Output: 2
Explanation:
  Split at 0: [10] vs [4,-8,7] → 10 >= 3 ✓
  Split at 1: [10,4] vs [-8,7] → 14 >= -1 ✓
  Split at 2: [10,4,-8] vs [7] → 6 >= 7 ✗

Example 2:

Input: nums = [2,3,1,0]
Output: 2
Explanation:
  Split at 0: [2] vs [3,1,0] → 2 >= 4 ✗
  Split at 1: [2,3] vs [1,0] → 5 >= 1 ✓
  Split at 2: [2,3,1] vs [0] → 6 >= 0 ✓

Constraints

  • 2 <= n <= 10^5
  • -10^5 <= nums[i] <= 10^5

Thinking Process

For each split index i, we need sum(nums[0..i]) >= sum(nums[i+1..n-1]). Computing both sums from scratch for every i would be O(n^2).

Two approaches to get O(n):

  1. Prefix sum array: precompute prefix sums, then leftSum = prefSum[i] and rightSum = prefSum[n-1] - prefSum[i]
  2. Running sums: maintain leftSum and rightSum, incrementally transferring each element from right to left
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Solution

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        int n = nums.size();
        vector<long long> prefSum(n);
        prefSum[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            prefSum[i] = prefSum[i - 1] + nums[i];
        }
        int count = 0;
        for (int i = 0; i < n - 1; i++) {
            long long leftSum = prefSum[i];
            long long rightSum = prefSum[n - 1] - prefSum[i];
            if (leftSum >= rightSum) {
                count++;
            }
        }
        return count;
    }
};

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: For each split index i, we need sum(nums[0..i]) >= sum(nums[i+1..n-1]). Computing both sums from scratch for every i would be O(n^2).

How the code works:

  1. Prefix sum array: precompute prefix sums, then leftSum = prefSum[i] and rightSum = prefSum[n-1] - prefSum[i]
  2. Running sums: maintain leftSum and rightSum, incrementally transferring each element from right to left

Walkthrough — input nums = [10,4,-8,7], expected output 2:

Split at 0: [10] vs [4,-8,7] → 10 >= 3 ✓ Split at 1: [10,4] vs [-8,7] → 14 >= -1 ✓ Split at 2: [10,4,-8] vs [7] → 6 >= 7 ✗

Why long long?

With n up to 10^5 and values up to pm 10^5, the total sum can reach pm 10^{10}, which overflows a 32-bit int. Using long long prevents this.

Comparison

Approach Time Space Notes
Prefix Sum Array O(n) O(n) Reusable for multiple queries
Running Sums O(n) O(1) Optimal for single pass

Common Mistakes

  • Using int instead of long long for sums (overflow)
  • Iterating to i < n instead of i < n - 1 (the right side must be non-empty)
  • Off-by-one in prefix sum indexing

Key Takeaways

  • “Compare left/right partition sums at every split” = prefix sum or running sum
  • The running sum approach is a space optimization: instead of storing all prefix sums, maintain two counters and transfer incrementally
  • Always check value ranges to decide if long long is needed

References

Template Reference