You are given a 0-indexed integer array nums of length n. The number of ways to partition nums is the number of pivot indices that satisfy both conditions:
1 <= pivot < nnums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]
You are also given an integer k. You can choose to change the value of one element of nums to k, or to leave the array unchanged.
Return the maximum possible number of ways to partition nums to satisfy both conditions after changing at most one element.
Example 1:
Input: nums = [2,-1,2], k = 3 Output: 1 Explanation: One optimal approach is to change nums[0] to k. The array becomes [3,-1,2]. There is one way to partition the array: - For pivot = 2, we have the partition [3,-1 | 2]: 3 + -1 == 2.
Example 2:
Input: nums = [0,0,0], k = 1 Output: 2 Explanation: The optimal approach is to leave the array unchanged. There are two ways to partition the array: - For pivot = 1, we have the partition [0 | 0,0]: 0 == 0 + 0. - For pivot = 2, we have the partition [0,0 | 0]: 0 + 0 == 0.
Example 3:
Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33 Output: 4 Explanation: One optimal approach is to change nums[2] to k. The array becomes [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14]. There are four ways to partition the array.
Constraints:
n == nums.length2 <= n <= 105-105 <= k, nums[i] <= 105
Similar Questions:
Given array A, we can compute an array diff where diff[i] = (A[0] + .. + A[i-1]) - (A[i] + .. + A[N-1]) (1 <= i < N), i.e. sum of left part minus sum of right part.
If we don't do any replacement, the answer is the number of 0s in the diff array.
If we replace A[i] with k, then diff[1] to diff[i] decrease by d, and diff[i+1] to diff[N-1] increase by d, where d = k - A[i]. Again, the answer is the number of 0s in this new diff array.
Instead of changing the diff array (taking O(N) time), we can simply count the number of d in diff[1..i] and number of -d in diff[(i+1)..(N-1)] (taking O(1) time).
So, we can use two frequency maps L and R which are the frequency maps of diff[1..i] and diff[(i+1)..(N-1)] respectively.
We scan from left to right. For each A[i], we try to update ans with L[d] + R[-d] where d = k - A[i], and update the frequency maps.
// OJ: https://leetcode.com/problems/maximum-number-of-ways-to-partition-an-array/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
int waysToPartition(vector<int>& A, int k) {
long sum = accumulate(begin(A), end(A), 0L), N = A.size();
unordered_map<long, int> L, R;
for (long i = 0, left = 0; i < N - 1; ++i) {
left += A[i];
long right = sum - left;
R[left - right]++;
}
int ans = R[0]; // If we don't do any replacement, answer is the number of `0`s in the frequency map
for (long i = 0, left = 0; i < N; ++i) {
left += A[i];
long right = sum - left, d = k - A[i];
ans = max(ans, L[d] + R[-d]); // If we replace `A[i]` with `k`, we will get `L[d] + R[-d]` pivots
R[left - right]--; // transfer the frequency from `R` to `L`.
L[left - right]++;
}
return ans;
}
};Example:
A = [2, -1, 2]
diff = [_, 1, -1]
If we change the diff array.
// replace A[0] with 3
A = [3, -1, 2]
diff change +1 +1
diff = [_, 2, 0]
// replace A[1] with 3
A = [2, 3, 2]
diff change -4 +4
diff = [_, -3, 3]
// replace A[2] with 3
A = [2, -1, 3]
diff change -1 -1
diff = [_, 0, -2]
If we use frequency maps:
diff = [_, 1, -1]
// If we don't do any replacement
[_ | 1, -1]
answer = R[0] = 0
// replace A[0] with 3, d = 1
[_ | 1, -1]
answer = L[1] + R[-1] = 0 + 1 = 1
// replace A[1] with 3, d = 4
[_ 1 | -1]
answer = L[4] + R[-4] = 0 + 0 = 0
// replace A[2] with 3, d = 1
[_ 1 -1 |]
answer = L[1] + R[-1] = 1 + 0 = 1