Problem Description
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. Return the number of partitions where the difference between the sum of the left and right subarrays is even.
Key Insights
- The sum difference between two subarrays is even if both sums are even or both sums are odd.
- The parity (even or odd) of the sum of the left subarray can be tracked as we iterate through possible partition indices.
- The total sum of the array can be used to derive the sum of the right subarray from the left subarray's sum.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
To solve the problem, we can use a single pass approach with prefix sums. As we iterate through the array, we keep track of the cumulative sum of the left subarray. We also calculate the total sum of the array to derive the sum of the right subarray. By checking the parity of the sums, we can count valid partitions. The algorithm uses two variables to track the count of even and odd sums.