Watch 10 video solutions for Count Partitions with Even Sum Difference, a easy level problem involving Array, Math, Prefix Sum. This walkthrough by codestorywithMIK has 3,344 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums of length n.
A partition is defined as an index i where 0 <= i < n - 1, splitting the array into two non-empty subarrays such that:
[0, i].[i + 1, n - 1].Return the number of partitions where the difference between the sum of the left and right subarrays is even.
Example 1:
Input: nums = [10,10,3,7,6]
Output: 4
Explanation:
The 4 partitions are:
[10], [10, 3, 7, 6] with a sum difference of 10 - 26 = -16, which is even.[10, 10], [3, 7, 6] with a sum difference of 20 - 16 = 4, which is even.[10, 10, 3], [7, 6] with a sum difference of 23 - 13 = 10, which is even.[10, 10, 3, 7], [6] with a sum difference of 30 - 6 = 24, which is even.Example 2:
Input: nums = [1,2,2]
Output: 0
Explanation:
No partition results in an even sum difference.
Example 3:
Input: nums = [2,4,6,8]
Output: 3
Explanation:
All partitions result in an even sum difference.
Constraints:
2 <= n == nums.length <= 1001 <= nums[i] <= 100Problem Overview: You split an array at index i into two parts: nums[0..i] and nums[i+1..n-1]. The task is to count how many split positions produce an even difference between the left and right sums.
Approach 1: Brute Force Sum Calculation (O(n²) time, O(1) space)
Check every possible partition index from 0 to n-2. For each split, iterate through the left part to compute leftSum and iterate again through the right part to compute rightSum. Calculate leftSum - rightSum and check if the result is even. This approach directly simulates the definition of the problem but repeatedly recomputes sums, leading to quadratic time. It works for small inputs but does unnecessary repeated work.
Approach 2: Prefix Sum Scan (O(n) time, O(1) space)
Precompute the total sum of the array, then scan once while maintaining a running prefix sum. At index i, the left sum is the current prefix and the right sum is total - prefix. Compute the difference and check if it is even. This avoids recomputing sums for each partition and reduces the complexity to linear time. The technique relies on the prefix sum pattern commonly used for range sum problems on an array.
Approach 3: Parity Observation with Math (O(n) time, O(1) space)
Expand the difference formula: left - right = left - (total - left) = 2 * left - total. Since 2 * left is always even, the parity of the difference depends entirely on total. If the total array sum is even, every partition produces an even difference. If the total is odd, none of them do. With this math insight, compute the total once and return n - 1 when it is even, otherwise 0. The scan itself becomes trivial because the answer depends only on the parity of the total sum.
Recommended for interviews: Start with the brute force explanation to show you understand how partitions and sums are computed. Then move to the prefix sum optimization, which is the expected linear-time solution pattern. Strong candidates usually go one step further and notice the parity simplification, reducing the reasoning to a constant-space mathematical observation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Sum Calculation | O(n²) | O(1) | Useful for explaining the raw partition logic before optimizing |
| Prefix Sum Scan | O(n) | O(1) | General solution when computing left and right sums efficiently |
| Parity / Math Observation | O(n) | O(1) | Best approach when you recognize the parity property of the difference formula |