LeetCode Problem 3432

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

Solution

LeetCode 3432 - Count Partitions with Even Sum Difference

Problem Understanding

The problem gives us an integer array nums of length n. We must consider every possible partition point between elements, where the array is split into two non-empty parts.

For a partition at index i:

• The left subarray is nums[0...i].
• The right subarray is nums[i+1...n-1].

For each partition, we compute:

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

We are interested only in partitions where this difference is an even number.

The task is to return the total number of valid partition positions.

The constraints are very small:

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

This means even a quadratic solution would be acceptable. However, the problem has a simple mathematical observation that allows us to solve it in linear time.

An important detail is that both subarrays must be non-empty. Therefore, valid partition indices are only from 0 to n - 2.

Some edge cases worth considering are:

• Arrays of length exactly 2, where only one partition exists.
• Arrays whose total sum is odd.
• Arrays whose total sum is even.
• Arrays containing only even numbers.
• Arrays containing only odd numbers.
• Situations where no partition satisfies the condition.

Understanding how parity behaves is the key to solving this problem efficiently.

Approaches

Brute Force

A straightforward solution is to examine every possible partition.

For each partition index:

1. Compute the sum of the left subarray.
2. Compute the sum of the right subarray.
3. Calculate their difference.
4. Check whether the difference is even.
5. Count it if valid.

This approach is correct because it directly follows the definition of a valid partition. Every possible partition is checked exactly once.

However, if we recompute sums from scratch for every partition, each partition requires O(n) work and there are O(n) partitions, leading to O(n²) time complexity.

Key Insight

Let:

• L = left subarray sum
• R = right subarray sum
• T = total array sum

Since:

$$R = T - L$$

the difference becomes:

$$L - R$$

Substituting:

$$L - (T - L)$$

$$2L - T$$

We need this value to be even.

Notice that 2L is always even regardless of the value of L.

Therefore, the parity of 2L - T depends only on T.

• If T is even, then 2L - T is always even.
• If T is odd, then 2L - T is always odd.

This means the validity of a partition does not depend on the partition location at all.

Therefore:

• If the total sum is even, every partition is valid.
• If the total sum is odd, no partition is valid.

Since there are exactly n - 1 possible partitions, the answer is simply:

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

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check every partition and recompute sums
Optimal	O(n)	O(1)	Use parity of the total sum

Algorithm Walkthrough

1. Compute the total sum of the array.
2. Check whether the total sum is even or odd.
3. If the total sum is odd, return 0.

The expression 2L - T will always be odd because 2L is even and T is odd. 4. If the total sum is even, return n - 1.

Every possible partition automatically produces an even difference.

Why it works

For any partition, the difference between the left and right sums is:

$$L - R = L - (T - L) = 2L - T$$

Since 2L is always even, the parity of the expression depends entirely on the parity of T.

If T is even, every partition produces an even difference. If T is odd, every partition produces an odd difference. Therefore counting valid partitions reduces to checking the parity of the total sum and returning either all possible partitions or none of them.

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 first computes the total sum of the array.

It then checks the parity of that sum using the modulo operator. If the total sum is even, every possible partition is valid, so the answer is simply len(nums) - 1, which is the number of positions between adjacent elements.

If the total sum is odd, no partition can produce an even difference, so the function returns 0.

The code directly implements the mathematical observation derived in the algorithm discussion.

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 follows the same logic as the Python version. It computes the total sum using a range loop and then checks whether the sum is even.

Integer overflow is not a concern because the maximum possible total sum is:

$$100 \times 100 = 10000$$

which easily fits within Go's int type.

Worked Examples

Example 1

Input:

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

Compute total sum:

Value	Running Sum
10	10
10	20
3	23
7	30
6	36

Total sum = 36

Since 36 is even, every partition is valid.

Number of partitions:

$$n - 1 = 5 - 1 = 4$$

Answer:

4

Example 2

Input:

nums = [1,2,2]

Compute total sum:

Value	Running Sum
1	1
2	3
2	5

Total sum = 5

Since 5 is odd, every partition difference is odd.

Answer:

0

Example 3

Input:

nums = [2,4,6,8]

Compute total sum:

Value	Running Sum
2	2
4	6
6	12
8	20

Total sum = 20

Since 20 is even, every partition is valid.

Number of partitions:

$$n - 1 = 4 - 1 = 3$$

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to compute the total sum
Space	O(1)	Only a few scalar variables are used

The algorithm performs a single traversal of the array to compute the total sum. After that, only a constant-time parity check is required. No additional data structures proportional to the input size are allocated, so the space usage remains constant.

Test Cases

sol = Solution()

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

assert sol.countPartitions([1, 1]) == 1  # minimum size, even total
assert sol.countPartitions([1, 2]) == 0  # minimum size, odd total

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

assert sol.countPartitions([1, 1, 1]) == 2  # odd count of odd values, even total
assert sol.countPartitions([1, 1, 1, 2]) == 0  # odd total sum

assert sol.countPartitions([100] * 100) == 99  # maximum length, even total
assert sol.countPartitions([99] * 100) == 99  # even total despite odd elements

assert sol.countPartitions([1] * 99 + [2]) == 0  # odd total sum

Test Summary

Test	Why
[10,10,3,7,6]	Verifies first example
[1,2,2]	Verifies no valid partitions
[2,4,6,8]	Verifies all partitions valid
[1,1]	Smallest array with even total
[1,2]	Smallest array with odd total
[2,2,2,2]	All values even
[1,1,1,1]	All values odd, even total
[1,1,1]	Even total from odd elements
[1,1,1,2]	Odd total sum case
[100] * 100	Maximum length stress test
[99] * 100	Large even total from odd values
[1] * 99 + [2]	Large odd total stress case

Edge Cases

Array of Length Two

When n = 2, there is exactly one possible partition. A common mistake is to overlook that the number of partition positions is n - 1, not n.

For example, [1,1] has one valid partition because the total sum is even. The implementation correctly returns 2 - 1 = 1.

Odd Total Sum

If the total sum is odd, it might be tempting to still inspect each partition individually. The mathematical derivation shows this is unnecessary.

For example, with [1,2,2], the total sum is 5. Every expression of the form 2L - 5 is odd, so no partition can ever be valid. The implementation immediately returns 0.

Even Total Sum

A programmer might incorrectly assume that some partitions are valid while others are not. The parity analysis proves that once the total sum is even, every partition is valid.

For example, [2,4,6,8] has total sum 20. Regardless of where the partition is placed, 2L - 20 remains even. The implementation therefore returns all possible partition positions, which is n - 1.

Arrays with Mixed Odd and Even Values

The parity of individual elements is irrelevant. Only the parity of the total sum matters.

For example, [1,1,1,1] consists entirely of odd numbers, yet the total sum is 4, which is even. Every partition is valid. The implementation naturally handles this because it depends only on the total sum parity.