2025. Maximum Number of Ways to Partition an Array LeetCode Solution
In this guide, you will get 2025. Maximum Number of Ways to Partition an Array LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Ways to Partition an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number of Ways to Partition an Array
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:
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.
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.length
2 <= n <= 105
-105 <= k, nums[i] <= 105
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2025. Maximum Number of Ways to Partition an Array LeetCode Solution in C++
class Solution {
public:
int waysToPartition(vector<int>& nums, int k) {
const int n = nums.size();
const long sum = accumulate(nums.begin(), nums.end(), 0L);
long prefix = 0;
// count of sum(A[0..k)) - sum(A[k..n)) for k in [0..i)
unordered_map<long, int> l;
// count of sum(A[0..k)) - sum(A[k..n)) for k in [i..n)
unordered_map<long, int> r;
for (int pivot = 1; pivot < n; ++pivot) {
prefix += nums[pivot - 1];
const long suffix = sum - prefix;
++r[prefix - suffix];
}
int ans = r[0];
prefix = 0;
for (const int num : nums) {
ans = max(ans, l[k - num] + r[num - k]);
prefix += num;
const long suffix = sum - prefix;
const long diff = prefix - suffix;
--r[diff];
++l[diff];
}
return ans;
}
}; /* code provided by PROGIEZ */
2025. Maximum Number of Ways to Partition an Array LeetCode Solution in Java
class Solution {
public int waysToPartition(int[] nums, int k) {
final int n = nums.length;
final long sum = Arrays.stream(nums).asLongStream().sum();
long prefix = 0;
// count of sum(A[0..k)) - sum(A[k..n)) for k in [0..i)
Map<Long, Integer> l = new HashMap<>();
// count of sum(A[0..k)) - sum(A[k..n)) for k in [i..n)
Map<Long, Integer> r = new HashMap<>();
for (int pivot = 1; pivot < n; ++pivot) {
prefix += nums[pivot - 1];
final long suffix = sum - prefix;
r.merge(prefix - suffix, 1, Integer::sum);
}
int ans = r.getOrDefault(0L, 0);
prefix = 0;
for (final int num : nums) {
final long change = (long) k - num;
ans = Math.max(ans, l.getOrDefault(change, 0) + r.getOrDefault(-change, 0));
prefix += num;
final long suffix = sum - prefix;
final long diff = prefix - suffix;
r.merge(diff, -1, Integer::sum);
l.merge(diff, 1, Integer::sum);
}
return ans;
}
} // code provided by PROGIEZ
2025. Maximum Number of Ways to Partition an Array LeetCode Solution in Python
class Solution:
def waysToPartition(self, nums: list[int], k: int) -> int:
n = len(nums)
summ = sum(nums)
prefix = 0
# Count of sum(A[0..k)) - sum(A[k..n)) for k in [0..i)
l = collections.Counter()
# Count of sum(A[0..k)) - sum(A[k..n)) for k in [i..n)
r = collections.Counter()
for pivot in range(1, n):
prefix += nums[pivot - 1]
suffix = summ - prefix
r[prefix - suffix] += 1
ans = r[0]
prefix = 0
for num in nums:
ans = max(ans, l[k - num] + r[num - k])
prefix += num
suffix = summ - prefix
diff = prefix - suffix
r[diff] -= 1
l[diff] += 1
return ans # code by PROGIEZ
