Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A partition is determined by its boundary between two consecutive elements. Moving that boundary one step transfers exactly one value from the right sum to the left sum, so both sums can be maintained without recomputing either side.

Approach

Initialize the left sum to zero and the right sum to the total array sum. For each index except the last, add its value to the left sum and subtract it from the right sum. Count the boundary when their difference is divisible by two.

Stopping before the last element ensures both parts remain nonempty. After each transfer, the two maintained sums represent precisely that partition. Their difference has the same parity as the total sum because it equals twice the left sum minus the total; the implementation still checks each boundary directly and returns the resulting count.

class Solution:
    def countPartitions(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        l = 0
        r = sum(nums)

        for i in range(n - 1):
            l += nums[i]
            r -= nums[i]
            if (l - r) % 2 == 0:
                res += 1

        return res

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(1) in both versions.