Skip to main content
Talentd

Count Partitions with Even Sum Difference - Solution & Explanation

EasyArrayMathPrefix Sum8 min readAsked at: Amazon, Microsoft, Accenture +2
Practice this problem

Problem Statement

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:

  • Left subarray contains indices [0, i].
  • Right subarray contains indices [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 <= 100
  • 1 <= nums[i] <= 100

Approach Overview

Problem 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.

Solution

We use two variables l and r to represent the sum of the left subarray and the right subarray, respectively. Initially, l = 0 and r = sum_{i=0}^{n-1} nums[i].

Next, we traverse the first n - 1 elements. Each time, we add the current element to the left subarray and subtract it from the right subarray. Then, we check if l - r is even. If it is, we increment the answer by one.

Finally, we return the answer.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Sum CalculationO(n²)O(1)Useful for explaining the raw partition logic before optimizing
Prefix Sum ScanO(n)O(1)General solution when computing left and right sums efficiently
Parity / Math ObservationO(n)O(1)Best approach when you recognize the parity property of the difference formula

Video Solution

Count Partitions with Even Sum Difference | Multiple Approaches | Leetcode 3432 | codestorywithMIK • codestorywithMIK • 3,484 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Partitions with Even Sum Difference easy or hard?
The problem is classified as Easy. The brute force idea is straightforward, and the optimal solution becomes very simple once you notice the parity property of the difference formula.
Count Partitions with Even Sum Difference Python/Java solution
Most implementations compute the total sum and then return n - 1 if the sum is even, otherwise 0. The logic is identical across Python, Java, C++, Go, or TypeScript because it relies only on integer arithmetic and array length.
How to solve Count Partitions with Even Sum Difference in O(n)?
First compute the total sum of the array. Using the identity left - right = 2 * left - total, observe that the difference is even only when the total sum is even. If total % 2 == 0, every split index from 0 to n-2 works, so return n - 1; otherwise return 0.
What is the best approach for Count Partitions with Even Sum Difference?
The optimal approach uses a simple math observation derived from prefix sums. Since left - right = 2 * left - total, the parity of the difference depends only on the total array sum. If the total sum is even, every split is valid, giving n - 1 partitions; otherwise the answer is 0. This runs in O(n) time to compute the total and O(1) extra space.
Is Count Partitions with Even Sum Difference asked at Google/Amazon/Meta?
Problems based on prefix sums, parity, and partition logic are common in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the underlying concepts of prefix sums and mathematical simplification are frequently tested.
What data structure is used in Count Partitions with Even Sum Difference?
The problem primarily uses arrays and prefix sum reasoning. No complex data structures are required because the solution only tracks cumulative sums and uses a mathematical parity observation.
What is the time complexity of Count Partitions with Even Sum Difference?
The optimal solution runs in O(n) time because you only need one pass to compute the total array sum. After that, determining the number of valid partitions is constant work. Space complexity is O(1) since no additional data structures are required.

Ready to solve this problem?

Practice Count Partitions with Even Sum Difference with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays