3432. Count Partitions with Even Sum Difference

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

Intuition

To solve this problem, we must determine how many ways we can split the array so that the difference in sums, between the left and right partitions, is even. An even number is divisible by two, and thus the sum of all elements of the array will determine how the array can be split. This means that:

Let l and r be the sum of the left and right subarrays, respectively.
Initially, l = 0 and r equals the sum of the entire array. This allows the left sum to start from zero and the right sum to start as the entire array.
We iterate through each element in the array (excluding the last one), adding to the left sum and simultaneously removing from the right sum. This action simulates shifting the partition index i.
After each shift in partition, we check if the difference l - r is even. If it is, we increase our count because we've found a valid partition.

The solution leverages a single iteration across the array while maintaining running totals of partition sums (l and r), simplifying the check for even difference by using a modulus operation.

Learn more about Math and Prefix Sum patterns.

Solution Approach

The solution uses a simple yet effective technique involving prefix sums to evaluate the difference between partitions at each possible split point:

Initialize Variables: We start with l = 0 (sum of the left subarray) and r = sum(nums) (sum of the right subarray). The variable ans is initialized to 0 to keep track of the count of valid partitions.
Iterate Over the Array: We loop through each element in nums except the last one. For each element x in nums[:-1]:
- Add x to l, updating the left sum: l += x.
- Subtract x from r, updating the right sum: r -= x.
Check Even Difference: After updating l and r at each step, check if the difference between them (l - r) is even. This is done using the modulus operation: (l - r) % 2 == 0. If this condition is true, it implies the difference is even and we increment the ans counter by 1.
Return Result: At the end of the loop, the value stored in ans is returned as the final result, indicating the number of valid partitions where the difference is even.

The implementation effectively runs in linear time O(n) and uses constant additional space O(1), making it efficient for large input sizes.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose nums = [4, 5, 6].

Initialize Variables:
- Start with l = 0 (the sum of the left subarray).
- Set r = sum(nums) = 4 + 5 + 6 = 15 (the sum of the right subarray).
- Initialize ans = 0 to count valid partitions.
Iterate Over the Array:
We loop through each element in nums except the last one. Let's go through each step:
- First Element (x = 4):
  - Update left sum: l = 0 + 4 = 4.
  - Update right sum: r = 15 - 4 = 11.
  - Check if the difference is even: (l - r) = (4 - 11) = -7; since -7 % 2 != 0, the difference is not even.
- Second Element (x = 5):
  - Update left sum: l = 4 + 5 = 9.
  - Update right sum: r = 11 - 5 = 6.
  - Check if the difference is even: (l - r) = (9 - 6) = 3; since 3 % 2 != 0, the difference is not even.
Return Result:
After iterating through the array, no valid partitions were found where the difference was even. Thus, ans = 0 is returned as the final result, indicating there are no partitions where the difference between the sum of the left and right subarrays is even.

Solution Implementation

1from typing import List
2
3class Solution:
4    def countPartitions(self, nums: List[int]) -> int:
5        # Initialize left sum as 0 (l) and right sum as the total sum of nums (r).
6        left_sum, right_sum = 0, sum(nums)
7      
8        # Initialize the answer counter to 0.
9        count_of_partitions = 0
10
11        # Iterate over the nums list until the second-to-last element.
12        for x in nums[:-1]:
13            # Add the current element to the left sum.
14            left_sum += x
15          
16            # Subtract the current element from the right sum.
17            right_sum -= x
18
19            # Check if the difference between left and right sums is even.
20            if (left_sum - right_sum) % 2 == 0:
21                # If true, increment the partitions count.
22                count_of_partitions += 1
23
24        # Return the total count of partitions.
25        return count_of_partitions
26

1class Solution {
2    public int countPartitions(int[] nums) {
3        // Initialize left sum and right sum
4        int leftSum = 0, rightSum = 0;
5      
6        // Calculate the total sum (rightSum) of the array
7        for (int num : nums) {
8            rightSum += num;
9        }
10      
11        // Initialize answer count
12        int answerCount = 0;
13      
14        // Iterate over the array till the second last element
15        for (int i = 0; i < nums.length - 1; ++i) {
16            // Update left sum by adding current element
17            leftSum += nums[i];
18          
19            // Update right sum by subtracting current element
20            rightSum -= nums[i];
21          
22            // Check if the difference between left sum and right sum is even
23            if ((leftSum - rightSum) % 2 == 0) {
24                // Increment the answer count if true
25                ++answerCount;
26            }
27        }
28      
29        // Return the number of partitions found
30        return answerCount;
31    }
32}
33

1#include <vector>
2#include <numeric> // for accumulate function
3
4class Solution {
5public:
6    // Method to count the number of partitions where the difference between the sum of the left and right partitions is even
7    int countPartitions(std::vector<int>& nums) {
8        int leftSum = 0; // Initialize the sum of the left partition
9        int rightSum = std::accumulate(nums.begin(), nums.end(), 0); // Calculate the total sum of the array (right partition initially includes all elements)
10        int count = 0; // Initialize the count of valid partitions
11
12        // Iterate through the array till the second last element
13        for (int i = 0; i < nums.size() - 1; ++i) {
14            leftSum += nums[i]; // Add current element to the left partition sum
15            rightSum -= nums[i]; // Subtract current element from the right partition sum
16          
17            // Check if the difference between left and right partitions is even
18            if ((leftSum - rightSum) % 2 == 0) {
19                ++count; // Increment count if the condition is satisfied
20            }
21        }
22        return count; // Return the number of valid partitions
23    }
24};
25

1function countPartitions(nums: number[]): number {
2    let leftSum = 0; // Sum of elements from the left part
3    let rightSum = nums.reduce((accumulator, currentValue) => accumulator + currentValue, 0); // Total sum of all elements in the array
4    let partitionCount = 0; // To count the number of valid partitions
5
6    // Iterate through the array, excluding the last element
7    for (const num of nums.slice(0, -1)) {
8        leftSum += num;  // Increment the left sum by the current number
9        rightSum -= num; // Decrement the right sum by the current number
10
11        // Check if the difference between the left and right sums is even
12        if ((leftSum - rightSum) % 2 === 0) {
13            partitionCount++; // Increment the partition count
14        }
15    }
16
17    return partitionCount; // Return the total number of valid partitions
18}
19

Time and Space Complexity

The time complexity of the code is O(n) because the code iterates over each element in the list nums exactly once, except for the last element, which results in linear time proportional to the length of nums.

The space complexity is O(1) because the code uses a constant amount of additional space regardless of the input size. The variables l, r, and ans are used for calculations and accumulate results, but their space usage does not scale with the input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know