3432: Count Partitions with Even Sum Difference

Difficulty: Easy

Topics: Arrays, Prefix Sum, Math

Companies: Google, Amazon, Microsoft

Pro Tip: The optimal solution for this problem runs in O(n) time with O(1) space by leveraging prefix sums and mathematical properties of even numbers.

Problem Statement

Given an integer array nums of length n, count the number of partitions where the difference between the sum of the left and right subarrays is even.

A partition is defined as an index i where 0 <= i < n - 1, splitting the array into:

Left subarray: indices [0, i]
Right subarray: indices [i + 1, n - 1]

Example 1

Input: nums = [10,10,3,7,6]
Output: 4
Explanation:
Partition at index 0: Left = [10], Right = [10,3,7,6], Difference = -16 (even)
Partition at index 1: Left = [10,10], Right = [3,7,6], Difference = 4 (even)
Partition at index 2: Left = [10,10,3], Right = [7,6], Difference = 10 (even)
Partition at index 3: Left = [10,10,3,7], Right = [6], Difference = 24 (even)

Example 2

Input: nums = [1,2,2]
Output: 0
Explanation: No partition results in an even difference.

Example 3

Input: nums = [2,4,6,8]
Output: 3

Problem Link: View on LeetCode ↗

Approach 1: Brute Force

Calculate sums for all possible partitions and check if their difference is even.

Algorithm Steps

Iterate through all possible partition indices
For each partition, calculate left and right sums
Check if the difference is even
Count valid partitions

Complexity Analysis

Time Complexity	Space Complexity
O(n²)	O(1)

Brute Force Solution

class Solution {
public:
    int countPartitions(vector<int>& nums) {
        int n = nums.size();
        int count = 0;

        for (int i = 0; i < n - 1; ++i) {
            int leftSum = 0, rightSum = 0;
            for (int j = 0; j <= i; ++j) {
                leftSum += nums[j];
            }
            for (int j = i + 1; j < n; ++j) {
                rightSum += nums[j];
            }
            if ((leftSum - rightSum) % 2 == 0) {
                ++count;
            }
        }

        return count;
    }
};

class Solution {
    public int countPartitions(int[] nums) {
        int n = nums.length;
        int count = 0;

        for (int i = 0; i < n - 1; i++) {
            int leftSum = 0, rightSum = 0;
            for (int j = 0; j <= i; j++) {
                leftSum += nums[j];
            }
            for (int j = i + 1; j < n; j++) {
                rightSum += nums[j];
            }
            if ((leftSum - rightSum) % 2 == 0) {
                count++;
            }
        }

        return count;
    }
}

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

Implementation Note: While straightforward, this approach is inefficient for large arrays due to its O(n²) time complexity from recalculating sums for each partition.

Approach 2: Prefix Sum

Optimize by precomputing prefix sums to calculate subarray sums in constant time.

Algorithm Steps

Compute prefix sum array
Calculate total sum of the array
For each partition, get left sum from prefix array
Right sum is total sum minus left sum
Check if difference is even

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(n)

Prefix Sum Solution

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

class Solution {
    public int countPartitions(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        prefix[0] = nums[0];
        
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }
        
        int totalSum = prefix[n - 1];
        int count = 0;
        
        for (int i = 0; i < n - 1; i++) {
            int leftSum = prefix[i];
            int rightSum = totalSum - leftSum;
            if ((leftSum - rightSum) % 2 == 0) {
                count++;
            }
        }
        
        return count;
    }
}

class Solution:
    def countPartitions(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * n
        prefix[0] = nums[0]
        
        for i in range(1, n):
            prefix[i] = prefix[i-1] + nums[i]
            
        totalSum = prefix[-1]
        count = 0
        
        for i in range(n - 1):
            leftSum = prefix[i]
            rightSum = totalSum - leftSum
            if (leftSum - rightSum) % 2 == 0:
                count += 1
                
        return count

Implementation Note: The prefix sum approach reduces time complexity to O(n) by avoiding repeated sum calculations, though it uses O(n) space for the prefix array.

Approach 3: Optimized Space (Mathematical Insight)

Further optimize by recognizing that (leftSum - rightSum) is even when (leftSum + rightSum) and (leftSum - rightSum) have the same parity.

Algorithm Steps

Calculate total sum of the array
Track cumulative left sum as we iterate
Right sum is total sum minus current left sum
Check if difference is even using mathematical properties

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(1)

Optimized Solution

class Solution {
public:
    int countPartitions(vector<int>& nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        int leftSum = 0;
        int count = 0;
        
        for (int i = 0; i < nums.size() - 1; ++i) {
            leftSum += nums[i];
            int rightSum = totalSum - leftSum;
            if ((leftSum - rightSum) % 2 == 0) {
                ++count;
            }
        }
        
        return count;
    }
};

class Solution {
    public int countPartitions(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        int leftSum = 0;
        int count = 0;
        
        for (int i = 0; i < nums.length - 1; i++) {
            leftSum += nums[i];
            int rightSum = totalSum - leftSum;
            if ((leftSum - rightSum) % 2 == 0) {
                count++;
            }
        }
        
        return count;
    }
}

class Solution:
    def countPartitions(self, nums: List[int]) -> int:
        totalSum = sum(nums)
        leftSum = 0
        count = 0
        
        for i in range(len(nums) - 1):
            leftSum += nums[i]
            rightSum = totalSum - leftSum
            if (leftSum - rightSum) % 2 == 0:
                count += 1
                
        return count

Key Insight: The difference (leftSum - rightSum) is even exactly when (leftSum + rightSum) and (leftSum - rightSum) have the same parity. Since totalSum = leftSum + rightSum, we can optimize further by just tracking the parity of leftSum.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	When to Use
Brute Force	O(n²)	O(1)	Only for small inputs or understanding
Prefix Sum	O(n)	O(n)	When space is not a concern
Optimized	O(n)	O(1)	Best for most cases

Interview Tip: When explaining the optimized solution, emphasize the mathematical insight that allows us to reduce the space complexity while maintaining linear time.

Edge Cases and Special Considerations

When implementing solutions for this problem, consider these edge cases:

1. Small Arrays

Input: nums = [1,1]
Output: 1
Explanation: Only one possible partition with difference 0 (even)

2. All Elements Same

Input: nums = [2,2,2,2]
Output: 3
Explanation: All partitions will have even difference (0)

3. No Valid Partitions

Input: nums = [1,3,5]
Output: 0
Explanation: All partitions result in odd differences

Important: Always test your solution with arrays of length 2 (minimum valid input) and arrays where all elements are identical, as these often reveal edge cases.

Visualization

The optimized approach works by maintaining a running left sum:

Initialization: Calculate total sum of the array
Iteration: For each element, add to left sum and compute right sum
Check: Verify if (leftSum - rightSum) is even
Result: Count of valid partitions where the condition holds

This approach efficiently tracks the necessary sums with minimal space usage.

Frequently Asked Questions

1. Why does (leftSum - rightSum) % 2 == 0 work?

The modulo operation checks the parity (evenness/oddness) of the difference. When the result is 0, the difference is even. This is equivalent to checking if leftSum and rightSum have the same parity.

2. Can this problem be solved with constant space?

Yes, the optimized approach uses O(1) space by maintaining only the total sum and a running left sum, without storing prefix sums.

3. How would you handle very large arrays?

The optimized O(n) time, O(1) space solution is ideal for large arrays as it processes the array in a single pass without additional storage.

4. What's the mathematical insight behind the optimization?

The key insight is that (leftSum - rightSum) is even when (leftSum + rightSum) is even (since leftSum - rightSum = 2*leftSum - totalSum). This allows us to just track the parity of leftSum.

5. Can this be extended to check for other difference conditions?

Yes, similar approaches can check for divisibility by other numbers (e.g., difference divisible by 3) by adjusting the modulo condition.

6. How does this compare to the "Equal Sum Partition" problem?

This problem is simpler as it only checks for even difference, not exact equality. The equal sum problem requires more complex dynamic programming.

7. What if we needed to return the partition indices?

We would store the indices where the condition is met rather than just counting them, but the core logic would remain the same.

8. Can this be parallelized for better performance?

For extremely large arrays, prefix sums can be computed in parallel, but the O(n) sequential solution is typically sufficient.

9. How would you test this code?

Test with arrays of varying lengths, including edge cases (length 2), arrays with all even/odd numbers, and mixed parity arrays to verify all conditions.

10. What's the practical application of this algorithm?

Similar partitioning problems appear in load balancing, database sharding, and parallel computing where you need to divide data with certain properties.

Final Thoughts: This problem demonstrates how mathematical insights can lead to significant optimizations in algorithm design. The progression from brute force to optimized solution shows the importance of analyzing problem constraints and properties.