Count Partitions with Even Sum Difference | Leetcode | Explanation and Solution

Partitioning arrays is a common problem in algorithm challenges, and counting partitions with an even sum difference is one of the interesting variations. 

Problem Statement

You are given an integer array nums of length n. A partition is defined as an index i where:

1. The left subarray contains elements from index [0, i].
2. The right subarray contains elements from index [i + 1, n - 1].

You need to find the number of such 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:
  • Partition at index 0: Left = [10], Right = [10, 3, 7, 6], Difference = -16 (even)
  • Partition at index 1: Left = [10, 10], Right = [3, 7, 6], Difference = 4 (even)
  • Partition at index 2: Left = [10, 10, 3], Right = [7, 6], Difference = 10 (even)
  • Partition at index 3: Left = [10, 10, 3, 7], Right = [6], Difference = 24 (even)

Example 2:

• Input: nums = [1,2,2]
• Output: 0
• Explanation: No partition results in an even difference.

Example 3:

• Input: nums = [2,4,6,8]
• Output: 3

---

Approach 1: Brute Force

In this approach, we manually calculate the left and right subarray sums for each possible partition.

1. Iterate over all possible indices i from 0 to n-2.
2. Compute the sum of the left and right subarrays.
3. Check if the difference (leftSum - rightSum) is even.
4. Count the partitions where the condition holds true.

Code:

class Solution {

public:

    int countPartitions(vector<int>& nums) {

        int n = nums.size();

        int count = 0;

        for (int i = 0; i < n - 1; ++i) {

            int leftSum = 0, rightSum = 0;

            for (int j = 0; j <= i; ++j) {

                leftSum += nums[j];

            }

            for (int j = i + 1; j < n; ++j) {

                rightSum += nums[j];

            }

            if ((leftSum - rightSum) % 2 == 0) {

                ++count;

            }

        }

        return count;

    }

};

Complexity:

• Time Complexity: $O(n^2)$, as for each partition, we compute the left and right sums.
• Space Complexity: $O(1)$, no additional space is used.

This approach works but is inefficient for large arrays.

---

Approach 2: Using Prefix Sum

To optimize the process, we can use a prefix sum array to calculate the sum of any subarray in constant time.

1. Construct a prefix sum array prefixSum, where prefixSum[i] stores the sum of elements from index 0 to i.
2. The left sum for partition i is prefixSum[i].
3. The right sum for partition i is totalSum - prefixSum[i], where totalSum is the sum of the entire array.
4. Check if (leftSum - rightSum) is even.

Code:

class Solution {

public:

    int countPartitions(vector<int>& nums) {

        int n = nums.size();

        vector<int> prefixSum(n, 0);

        prefixSum[0] = nums[0];

        for (int i = 1; i < n; ++i) {

            prefixSum[i] = prefixSum[i - 1] + nums[i];

        }

        int totalSum = prefixSum[n - 1];

        int count = 0;

        for (int i = 0; i < n - 1; ++i) {

            int leftSum = prefixSum[i];

            int rightSum = totalSum - leftSum;

            if ((leftSum - rightSum) % 2 == 0) {

                ++count;

            }

        }

        return count;

    }

};

Complexity:

• Time Complexity: $O(n)$, prefix sum is calculated in $O(n)$, and partition check is also $O(n)$.
• Space Complexity: $O(n)$, for the prefix sum array.

---

Approach 3: Optimized Space

Instead of using a prefix sum array, we can keep track of the left sum and right sum using simple variables. This reduces the space complexity.

Code:

class Solution {

public:

    int countPartitions(vector<int>& nums) {

        int n = nums.size();

        int totalSum = 0;

        for (int num : nums) {

            totalSum += num;

        }

        int leftSum = 0, count = 0;

        for (int i = 0; i < n - 1; ++i) {

            leftSum += nums[i];

            int rightSum = totalSum - leftSum;

            if ((leftSum - rightSum) % 2 == 0) {

                ++count;

            }

        }

        return count;

    }

};

Complexity:

• Time Complexity: $O(n)$, single iteration over the array.
• Space Complexity: $O(1)$, no additional space used.