Problem Description

You have an integer array nums with length n. You need to find valid ways to split this array into two parts.

A partition is a split point at index i (where 0 <= i < n - 1) that divides the array into:

• Left subarray: elements from index 0 to i (inclusive)
• Right subarray: elements from index i + 1 to n - 1 (inclusive)

Both subarrays must be non-empty after the split.

For each partition, calculate:

• Sum of all elements in the left subarray
• Sum of all elements in the right subarray
• The difference between these two sums (left sum minus right sum)

Your task is to count how many partitions result in an even difference between the left and right subarray sums.

For example, if nums = [1, 2, 3, 4]:

• Partition at index 0: left = [1] (sum = 1), right = [2, 3, 4] (sum = 9), difference = 1 - 9 = -8 (even)
• Partition at index 1: left = [1, 2] (sum = 3), right = [3, 4] (sum = 7), difference = 3 - 7 = -4 (even)
• Partition at index 2: left = [1, 2, 3] (sum = 6), right = [4] (sum = 4), difference = 6 - 4 = 2 (even)

All three partitions have even differences, so the answer would be 3.

Intuition

The key insight is that we don't need to recalculate the sums from scratch for each partition point. As we move the partition point from left to right, we're essentially moving one element from the right subarray to the left subarray.

Think about what happens when we move from one partition to the next:

• The left sum increases by the element we just added
• The right sum decreases by the same element

Initially, we can start with:

• l = 0 (empty left subarray)
• r = sum(nums) (entire array as right subarray)

Then, for each partition at index i:

• Add nums[i] to the left sum: l += nums[i]
• Subtract nums[i] from the right sum: r -= nums[i]
• Check if the difference l - r is even

The beauty of this approach is that we maintain running sums instead of recalculating them each time. This transforms what could be an O(n²) problem (calculating sums for each partition) into an O(n) solution.

To check if a number is even, we simply use the modulo operator: (l - r) % 2 == 0. If the remainder when divided by 2 is 0, the difference is even.

We iterate through the first n-1 elements (not the last one) because a partition requires both subarrays to be non-empty. If we included the last element, the right subarray would be empty, which violates the problem constraints.

Learn more about Math and Prefix Sum patterns.

Solution Approach

We implement the solution using the prefix sum technique with running totals.

Step 1: Initialize the sums

• Set l = 0 to represent the initial left subarray sum (empty at start)
• Set r = sum(nums) to represent the initial right subarray sum (contains all elements)
• Initialize ans = 0 to count valid partitions

Step 2: Iterate through partition points We loop through nums[:-1] (all elements except the last one) because:

• Each element represents a potential partition point
• We exclude the last element since the right subarray cannot be empty

Step 3: Update sums for each partition For each element x at the current position:

• Add it to the left sum: l += x
• Remove it from the right sum: r -= x

This efficiently maintains the sums without recalculating from scratch.

Step 4: Check if the difference is even

• Calculate the difference: l - r
• Check if it's even using modulo: (l - r) % 2 == 0
• If true, increment the answer counter: ans += 1

In Python, we can simplify this to ans += (l - r) % 2 == 0 since boolean True is treated as 1 and False as 0.

Step 5: Return the result After checking all valid partition points, return ans.

Time Complexity: O(n) - we traverse the array twice (once for initial sum, once for partitions) Space Complexity: O(1) - we only use a constant amount of extra space for variables

Example Walkthrough

Let's walk through the solution with nums = [2, 5, 3, 8]:

Initial Setup:

• l = 0 (left sum starts empty)
• r = 2 + 5 + 3 + 8 = 18 (right sum contains all elements)
• ans = 0 (counter for valid partitions)

Partition at index 0 (split after element 2):

• Move element 2 from right to left
• l = 0 + 2 = 2
• r = 18 - 2 = 16
• Difference: l - r = 2 - 16 = -14
• Is -14 even? Yes! (-14 % 2 == 0)
• ans = 1

Partition at index 1 (split after element 5):

• Move element 5 from right to left
• l = 2 + 5 = 7
• r = 16 - 5 = 11
• Difference: l - r = 7 - 11 = -4
• Is -4 even? Yes! (-4 % 2 == 0)
• ans = 2

Partition at index 2 (split after element 3):

• Move element 3 from right to left
• l = 7 + 3 = 10
• r = 11 - 3 = 8
• Difference: l - r = 10 - 8 = 2
• Is 2 even? Yes! (2 % 2 == 0)
• ans = 3

We stop here (don't partition at index 3) because that would leave the right subarray empty.

Result: All 3 partitions have even differences, so we return 3.

Notice how we never recalculated the entire sums - we just adjusted them by adding/subtracting the current element as we moved the partition point. This running sum technique makes our solution efficient at O(n) time complexity.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The algorithm performs the following operations:

• Computing the initial sum of all elements: O(n)
• Iterating through the first n-1 elements of the array: O(n-1)
• For each iteration, performing constant time operations (addition, subtraction, modulo, comparison): O(1)

Therefore, the overall time complexity is O(n) + O(n-1) × O(1) = O(n).

Space Complexity: O(1).

The algorithm uses only a fixed amount of extra space:

• Three integer variables: l, r, and ans
• One loop variable: x

These variables do not depend on the input size, so the space complexity is constant O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Iterating Through All Elements Instead of n-1

The Pitfall: A common mistake is iterating through the entire array, including the last element:

# INCORRECT - iterates through all elements
for num in nums:
    left_sum += num
    right_sum -= num
    partition_count += (left_sum - right_sum) % 2 == 0

Why It's Wrong:

• When processing the last element, the right subarray becomes empty
• This violates the constraint that both subarrays must be non-empty
• It counts an invalid partition where all elements are in the left subarray

The Solution: Always exclude the last element from iteration:

# CORRECT - excludes the last element
for num in nums[:-1]:
    left_sum += num
    right_sum -= num
    partition_count += (left_sum - right_sum) % 2 == 0

2. Integer Overflow in Other Languages

The Pitfall: While Python handles arbitrary-precision integers automatically, implementing this in languages like C++ or Java can cause overflow:

// In C++ - potential overflow
int left_sum = 0;
int right_sum = accumulate(nums.begin(), nums.end(), 0);

The Solution: Use appropriate data types to prevent overflow:

// Use long long in C++
long long left_sum = 0;
long long right_sum = accumulate(nums.begin(), nums.end(), 0LL);

3. Checking Parity Incorrectly

The Pitfall: Incorrectly checking if the difference is even, especially with negative numbers:

# INCORRECT - doesn't handle negative differences properly in some languages
partition_count += (left_sum - right_sum) & 1 == 0  # Bitwise AND might have precedence issues

The Solution: Use modulo operator with proper parentheses:

# CORRECT - handles all cases including negative differences
partition_count += (left_sum - right_sum) % 2 == 0

4. Off-by-One Error in Index-Based Implementation

The Pitfall: When using indices instead of values, forgetting the correct boundary:

# INCORRECT - wrong range
for i in range(len(nums)):  # Should be range(len(nums) - 1)
    left_sum += nums[i]
    right_sum -= nums[i]

The Solution: Ensure the loop stops before the last element:

# CORRECT - proper range
for i in range(len(nums) - 1):
    left_sum += nums[i]
    right_sum -= nums[i]