Count Partitions with Even Sum Difference

Difficulty: Easy | Acceptance: 85.20% | Paid: No Topics: Array, Math, Prefix Sum

You are given a 0-indexed integer array nums of length n.

A partition of an array is a way to split the array into two non-empty contiguous subarrays. The sum difference of a partition is the absolute difference between the sum of the left subarray and the sum of the right subarray.

Return the number of partitions where the sum difference is even.

• Table of Contents
• Examples
• Constraints
• Mathematical Observation
• Prefix Sum Approach
• Brute Force Approach

Examples

Example 1:

Input: nums = [1, 2, 3]
Output: 2
Explanation: There are 2 partitions with even sum difference:
- Split after index 0: left = [1], right = [2, 3], |1 - 5| = 4 (even)
- Split after index 1: left = [1, 2], right = [3], |3 - 3| = 0 (even)

Example 2:

Input: nums = [1, 1, 1]
Output: 0
Explanation: There are 0 partitions with even sum difference:
- Split after index 0: left = [1], right = [1, 1], |1 - 2| = 1 (odd)
- Split after index 1: left = [1, 1], right = [1], |2 - 1| = 1 (odd)

Example 3:

Input: nums = [2, 4, 6]
Output: 2
Explanation: There are 2 partitions with even sum difference:
- Split after index 0: left = [2], right = [4, 6], |2 - 10| = 8 (even)
- Split after index 1: left = [2, 4], right = [6], |6 - 6| = 0 (even)

Constraints

2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Mathematical Observation

Intuition The absolute difference |a - b| is even if and only if a and b have the same parity (both even or both odd). Since sum(left) + sum(right) = total_sum, both sums have the same parity exactly when total_sum is even.

Steps

• Calculate the total sum of all elements in the array
• If total sum is odd, return 0 (no valid partitions)
• If total sum is even, return n - 1 (all partitions are valid)

class Solution:
    def countPartitions(self, nums: list[int]) -> int:
        total = sum(nums)
        if total % 2 == 1:
            return 0
        return len(nums) - 1

Complexity

• Time: O(n)
• Space: O(1)
• Notes: This is the optimal solution with constant space and linear time complexity.

Prefix Sum Approach

Intuition Use prefix sums to efficiently calculate the sum of left and right subarrays for each possible partition point, then check if their difference is even.

Steps

• Calculate prefix sums where prefix[i] is the sum of elements from index 0 to i-1
• For each split point i from 1 to n-1, calculate left sum as prefix[i] and right sum as total - prefix[i]
• Check if |left - right| is even and count valid partitions

class Solution:
    def countPartitions(self, nums: list[int]) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        total = prefix[n]
        count = 0
        
        for i in range(1, n):
            left_sum = prefix[i]
            right_sum = total - left_sum
            if abs(left_sum - right_sum) % 2 == 0:
                count += 1
        
        return count

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses O(n) extra space for prefix sums, but can be optimized to O(1) space.

Brute Force Approach

Intuition For each possible partition point, calculate the sum of left and right subarrays separately and check if their difference is even.

Steps

• Initialize count to 0
• For each split point i from 1 to n-1:
  • Calculate left sum by iterating from 0 to i-1
  • Calculate right sum by iterating from i to n-1
  • Check if |left - right| is even and increment count
• Return count

class Solution:
    def countPartitions(self, nums: list[int]) -> int:
        n = len(nums)
        count = 0
        
        for i in range(1, n):
            left_sum = sum(nums[:i])
            right_sum = sum(nums[i:])
            if abs(left_sum - right_sum) % 2 == 0:
                count += 1
        
        return count

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: This approach has quadratic time complexity and may time out for large inputs, but demonstrates the brute force concept clearly.