LeetCode 3432 - Count Partitions with Even Sum Difference

Difficulty: 🟢 Easy
Topics: Array, Math, Prefix Sum

Solution

Problem Understanding

The problem gives us an integer array nums and asks us to count how many valid partition points produce an even difference between the sum of the left part and the sum of the right part.

A partition is created by choosing an index i such that:

The left subarray is nums[0:i+1]
The right subarray is nums[i+1:n]
Both subarrays must be non-empty

Since the array length is n, there are exactly n - 1 possible partition positions.

For every partition, we compute:

$$\text{difference} = \text{leftSum} - \text{rightSum}$$

We must count how many of these differences are even numbers.

The input constraints are very small:

2 <= n <= 100
1 <= nums[i] <= 100

These constraints tell us that even an $O(n^2)$ solution would pass comfortably. However, the problem has a very elegant mathematical observation that allows an $O(n)$ solution with constant extra space.

An important detail is that we only care whether the difference is even or odd, not the exact value. This parity observation simplifies the problem significantly.

There are several edge cases worth thinking about immediately:

Arrays with only two elements, since there is only one possible partition.
Arrays where all numbers are odd.
Arrays where all numbers are even.
Cases where no partition works.
Cases where every partition works.

The problem guarantees all numbers are positive integers, so we do not need to handle empty arrays or negative indexing issues.

Approaches

Brute Force Approach

The most direct solution is to try every partition.

For each partition index i:

Compute the sum of the left subarray.
Compute the sum of the right subarray.
Check whether their difference is even.
If it is even, increment the answer.

A naive implementation recomputes sums repeatedly, which costs $O(n)$ work per partition. Since there are $n - 1$ partitions, the total complexity becomes $O(n^2)$.

This approach is correct because it explicitly evaluates every valid partition exactly as defined in the problem statement.

Even though the constraints are small enough for this to pass, it is inefficient because we repeatedly sum overlapping portions of the array.

Key Insight for the Optimal Approach

The important mathematical observation is:

$$(\text{leftSum} - \text{rightSum}) \text{ is even}$$

A difference between two integers is even when both numbers have the same parity.

That means:

even - even = even
odd - odd = even

Now let:

$$\text{totalSum} = \text{leftSum} + \text{rightSum}$$

Since:

$$\text{rightSum} = \text{totalSum} - \text{leftSum}$$

Then:

$$\text{leftSum} - \text{rightSum} = \text{leftSum} - (\text{totalSum} - \text{leftSum}) = 2 \cdot \text{leftSum} - \text{totalSum}$$

The term $2 \cdot \text{leftSum}$ is always even.

Therefore, the parity of the expression depends entirely on totalSum.

This means:

If totalSum is even, every partition works.
If totalSum is odd, no partition works.

So the answer becomes extremely simple:

Return n - 1 if total sum is even.
Return 0 otherwise.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Computes sums for every partition independently
Optimal	O(n)	O(1)	Uses parity observation on total sum

Algorithm Walkthrough

Optimal Algorithm

Compute the total sum of the array.

We first calculate the sum of all elements because the parity of the partition difference depends entirely on the parity of the total sum. 2. Check whether the total sum is even.

Using modulo:

totalSum % 2 == 0

If this condition is true, then every valid partition will produce an even difference. 3. Return the number of possible partitions.

An array of length n has exactly n - 1 valid partition positions because both sides must remain non-empty. 4. Otherwise, return 0.

If the total sum is odd, then no partition can produce an even difference.

Why it works

The key invariant is that:

$$\text{leftSum} - \text{rightSum} = 2 \cdot \text{leftSum} - \text{totalSum}$$

Since $2 \cdot \text{leftSum}$ is always even, the parity of the entire expression depends only on totalSum.

Therefore:

Even total sum means every partition difference is even.
Odd total sum means every partition difference is odd.

This guarantees the correctness of the algorithm.

Python Solution

from typing import List

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

The implementation is extremely concise because of the parity observation.

First, we compute the total sum of the array using Python's built-in sum() function.

Next, we check whether the total sum is even using modulo % 2.

If the total sum is even, every partition is valid, so we return len(nums) - 1, which represents all possible partition positions.

If the total sum is odd, no partition works, so we return 0.

The implementation directly follows the mathematical proof developed earlier.

Go Solution

func countPartitions(nums []int) int {
    totalSum := 0

    for _, num := range nums {
        totalSum += num
    }

    if totalSum%2 == 0 {
        return len(nums) - 1
    }

    return 0
}

The Go implementation mirrors the Python solution closely.

Since Go does not provide a built-in sum() function for slices, we manually iterate through the array and accumulate the total sum.

Integer overflow is not a concern because the constraints are tiny:

Maximum array length is 100
Maximum value is 100
Maximum total sum is only 10,000

Go slices are naturally used for the input array, and no additional memory allocation is required.

Worked Examples

Example 1

Input:

nums = [10, 10, 3, 7, 6]

First compute the total sum:

$$10 + 10 + 3 + 7 + 6 = 36$$

Since 36 is even, every partition is valid.

There are 5 - 1 = 4 partitions.

Partition Index	Left Sum	Right Sum	Difference	Even?
0	10	26	-16	Yes
1	20	16	4	Yes
2	23	13	10	Yes
3	30	6	24	Yes

Final answer:

Example 2

Input:

nums = [1, 2, 2]

Compute total sum:

$$1 + 2 + 2 = 5$$

Since 5 is odd, no partition can produce an even difference.

Partition Index	Left Sum	Right Sum	Difference	Even?
0	1	4	-3	No
1	3	2	1	No

Final answer:

Example 3

Input:

nums = [2, 4, 6, 8]

Compute total sum:

$$2 + 4 + 6 + 8 = 20$$

Since 20 is even, every partition works.

There are 4 - 1 = 3 valid partition positions.

Partition Index	Left Sum	Right Sum	Difference	Even?
0	2	18	-16	Yes
1	6	14	-8	Yes
2	12	8	4	Yes

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We compute the array sum once
Space	O(1)	Only a few integer variables are used

The algorithm only performs a single pass through the array to compute the total sum. After that, all operations are constant time.

No auxiliary data structures are needed, so the extra space usage remains constant.

Test Cases

from typing import List

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

sol = Solution()

assert sol.countPartitions([10,10,3,7,6]) == 4  # provided example, all partitions valid
assert sol.countPartitions([1,2,2]) == 0        # provided example, no valid partitions
assert sol.countPartitions([2,4,6,8]) == 3      # provided example, all partitions valid

assert sol.countPartitions([1,1]) == 1          # smallest valid array, even total
assert sol.countPartitions([1,2]) == 0          # smallest valid array, odd total

assert sol.countPartitions([2,2,2]) == 2        # all even numbers
assert sol.countPartitions([1,1,1,1]) == 3      # all odd numbers but even total
assert sol.countPartitions([1,1,1]) == 0        # all odd numbers with odd total

assert sol.countPartitions([100]*100) == 99     # maximum size with even total
assert sol.countPartitions([99]*99 + [100]) == 0  # large odd total

assert sol.countPartitions([5,5,5,5,5,5]) == 5 # repeated values, even total

Test Summary

Test	Why
`[10,10,3,7,6]`	Verifies standard case where all partitions work
`[1,2,2]`	Verifies case where no partitions work
`[2,4,6,8]`	Confirms even total implies all partitions valid
`[1,1]`	Smallest valid input with success
`[1,2]`	Smallest valid input with failure
`[2,2,2]`	All even values
`[1,1,1,1]`	All odd values but even total
`[1,1,1]`	Odd total sum case
`[100]*100`	Maximum input size
`[99]*99 + [100]`	Large input with odd total
`[5,5,5,5,5,5]`	Repeated values

Edge Cases

Minimum Length Array

The smallest possible array has length 2, meaning there is exactly one possible partition.

For example:

[1, 1]

A buggy implementation might incorrectly allow empty subarrays or mishandle partition boundaries. Our implementation avoids this because it directly returns n - 1 valid partitions when the total sum is even.

Odd Total Sum

An odd total sum guarantees that every partition difference will also be odd.

For example:

[1, 2, 2]

A naive implementation that individually checks partitions could still work, but it misses the global parity property. Our implementation handles this immediately with one parity check and returns 0.

All Partitions Valid

When the total sum is even, every partition is automatically valid.

For example:

[2, 4, 6, 8]

Some implementations may unnecessarily compute every left and right sum separately. Our solution correctly recognizes that parity alone determines the result and simply returns n - 1.