Maximum Number of Ways to Partition an Array solution and explanation
Google
4 more videos on this problem
LeetCode 2025. Maximum Number of Ways to Partition an ArrayHappy Coding · 25:53 · 4K views
2025. Maximum Number of Ways to Partition an Array (Leetcode Hard)Programming Live with Larry · 24:58 · 1K views
【每日一题】LeetCode 2025. Maximum Number of Ways to Partition an Array 10/7/2021Huifeng Guan · 22:39 · 1K views
leetcode 2025 -: Maximum Number of Ways to Partition an Array (Hard) !! meow meow explanationKartiK🗿 · 25:49 · 368 views
LeetCode 2025 | Maximum Number of Ways to Partition an Array | Optimized ApproachCodehurdle · 22:19 · 110 views
The problem
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
Approach overview
Problem Overview: You are given an integer array and a value k. You may change at most one element to k. After the change, count how many ways the array can be partitioned into two parts with equal sums. The goal is to maximize this count.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
The direct strategy tries every possible modification and checks all partition points. For each index, temporarily replace nums[i] with k, recompute the total sum, then iterate through the array to count indices where the prefix sum equals half of the total. This requires recalculating prefix sums repeatedly, leading to O(n) work per modification and O(n) possible modifications. While conceptually simple, the O(n²) runtime becomes impractical for large inputs. This approach mainly helps you understand how partition points depend on prefix sums and total sum differences.
Approach 2: Prefix Sum Calculation (O(n) time, O(n) space)
The key observation: a partition at index i is valid when the left prefix sum equals the right suffix sum. Let total be the sum of the array and prefix[i] the sum up to index i. The difference diff = prefix[i] - (total - prefix[i]) determines whether a partition is balanced. Using a frequency map of these differences lets you count valid splits quickly. If you change nums[j] to k, the total sum shifts by delta = k - nums[j]. That adjustment affects partitions differently depending on whether they lie to the left or right of j. By precomputing prefix differences and tracking counts in hash maps, you can evaluate the effect of each modification in constant time. This relies heavily on prefix sum computation and hash table frequency tracking.
Approach 3: Two-Pass Solution with Adjustment Maps (O(n) time, O(n) space)
An optimized implementation performs two passes across the array. First pass: compute prefix sums and build a map counting how many partition points produce each difference value. Second pass: simulate changing each index to k. Maintain two maps—one for partition differences to the left of the current index and one for the right. When applying the modification delta, partitions on the left require a difference of delta, while partitions on the right require -delta. A constant-time lookup in both maps gives the number of valid partitions for that modification. Update maps as you move forward. This method combines array traversal with prefix-difference counting to achieve linear time.
Recommended for interviews: Interviewers expect the prefix-sum + hash-map strategy with difference counting. Explaining the brute-force method first shows understanding of how partitions work. Transitioning to the linear-time solution demonstrates algorithmic optimization and familiarity with prefix-sum transformations.
Approach 1: Prefix Sum Calculation
This approach employs prefix sums to quickly determine the sum of any given subarray. By precomputing these sums, we can efficiently check the pivot conditions across the array in linear time.
The idea is to compute prefix sums for the array, then iterate through each potential pivot point to see if the sums match. Also, consider changing one element to the given k and see how many more valid partition points it provides.
def max_num_ways(nums, k):
n = len(nums)
total_sum = sum(nums)
prefix_sum = 0
result = 0
left_balances = {}
for i in range(n - 1):
prefix_sum += nums[i]
if prefix_sum == total_sum - prefix_sum:
result += 1
left_balances[prefix_sum] = left_balances.get(prefix_sum, 0) + 1
original_result = result
result = original_result
prefix_sum = 0
for i in range(n):
new_prefix_sum = prefix_sum + k - nums[i]
if new_prefix_sum == (total_sum + k - nums[i]) - new_prefix_sum:
result += 1
prefix_sum += nums[i]
if (total_sum + k - nums[i]) // 2 in left_balances:
result += left_balances[(total_sum + k - nums[i]) // 2]
if prefix_sum in left_balances:
left_balances[prefix_sum] -= 1
if left_balances[prefix_sum] == 0:
del left_balances[prefix_sum]
return result
nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14]
k = -33
print(max_num_ways(nums, k))import java.util.HashMap;
public class Solution {
public int maxNumWays(int[] nums, int k) {
int n = nums.length;
long totalSum = 0;
for (int num : nums) {
totalSum += num;
}
HashMap<Long, Integer> left_balances = new HashMap<>();
long prefixSum = 0;
int result = 0;
for (int i = 0; i < n - 1; i++) {
prefixSum += nums[i];
if (prefixSum * 2 == totalSum) {
result++;
}
left_balances.putIfAbsent(prefixSum, 0);
left_balances.put(prefixSum, left_balances.get(prefixSum) + 1);
}
int originalResult = result;
prefixSum = 0;
for (int i = 0; i < n; i++) {
long newPrefixSum = prefixSum + k - nums[i];
if (newPrefixSum * 2 == totalSum + k - nums[i]) {
result++;
}
prefixSum += nums[i];
if (left_balances.containsKey((totalSum + k - nums[i]) / 2)) {
result += left_balances.get((totalSum + k - nums[i]) / 2);
}
if (left_balances.containsKey(prefixSum)) {
left_balances.put(prefixSum, left_balances.get(prefixSum) - 1);
if (left_balances.get(prefixSum) == 0) {
left_balances.remove(prefixSum);
}
}
}
return Math.max(result, originalResult);
}
public static void main(String[] args) {
int[] nums = {22, 4, -25, -20, -15, 15, -16, 7, 19, -10, 0, -13, -14};
int k = -33;
Solution sol = new Solution();
System.out.println(sol.maxNumWays(nums, k));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int maxNumWays(vector<int>& nums, int k) {
int n = nums.size();
long long totalSum = 0;
unordered_map<long long, int> left_balances;
for (int num : nums) totalSum += num;
long long prefixSum = 0;
int result = 0;
for (int i = 0; i < n - 1; ++i) {
prefixSum += nums[i];
if (prefixSum * 2 == totalSum) {
++result;
}
++left_balances[prefixSum];
}
int originalResult = result;
prefixSum = 0;
for (int i = 0; i < n; ++i) {
long long newPrefixSum = prefixSum + k - nums[i];
if (newPrefixSum * 2 == totalSum + k - nums[i]) {
++result;
}
prefixSum += nums[i];
long long target = (totalSum + k - nums[i]) / 2;
if (left_balances.find(target) != left_balances.end()) {
result += left_balances[target];
}
if (left_balances.find(prefixSum) != left_balances.end()) {
if (--left_balances[prefixSum] == 0) {
left_balances.erase(prefixSum);
}
}
}
return max(result, originalResult);
}
int main() {
vector<int> nums = {22, 4, -25, -20, -15, 15, -16, 7, 19, -10, 0, -13, -14};
int k = -33;
cout << maxNumWays(nums, k) << endl;
return 0;
}The code calculates prefix sums for the array and maintains balances while checking potential pivots. Using a dictionary, we keep track of occurrences of prefix sums to adjust our pivots.
Time Complexity: O(n), where n is the length of the input array, due to a single pass to compute prefix sums and another to adjust with k.
Space Complexity: O(n), as we store prefix sums in a dictionary.
Approach 2: Two-Pass Solution with Adjustment
A different perspective on this problem uses a two-pass approach. First, find all valid pivot points without changes, then reassess the adjusted sums by testing each element change to k to find additional valid pivot positions.
function maxNumWays(nums, k) {
const n = nums.length;
let totalSum = nums.reduce((sum, num) => sum + num, 0);
let maxWays = 0;
let prefixSum = 0;
for (let pivot = 1; pivot < n; pivot++) {
prefixSum += nums[pivot - 1];
if (prefixSum * 2 === totalSum) {
maxWays++;
}
}
let originalMaxWays = maxWays;
prefixSum = 0;
for (let i = 0; i < n; i++) {
const adjustedTotal = totalSum + k - nums[i];
const adjustedPrefix = prefixSum + k - nums[i];
if (adjustedPrefix * 2 === adjustedTotal) {
maxWays++;
}
prefixSum += nums[i];
}
return Math.max(originalMaxWays, maxWays);
}
const nums = [22, 4, -25, -20, -15, 15, -16, 7, 19, -10, 0, -13, -14];
const k = -33;
console.log(maxNumWays(nums, k));using System;
public class Solution {
public int MaxNumWays(int[] nums, int k) {
int n = nums.Length;
long totalSum = 0;
foreach (int num in nums) totalSum += num;
int maxWays = 0;
long prefixSum = 0;
for (int pivot = 1; pivot < n; pivot++) {
prefixSum += nums[pivot - 1];
if (2 * prefixSum == totalSum) maxWays++;
}
int originalMaxWays = maxWays;
prefixSum = 0;
for (int i = 0; i < n; i++) {
long adjustedTotal = totalSum + k - nums[i];
long adjustedPrefix = prefixSum + k - nums[i];
if (2 * adjustedPrefix == adjustedTotal) maxWays++;
prefixSum += nums[i];
}
return Math.Max(originalMaxWays, maxWays);
}
public static void Main(string[] args) {
int[] nums = {22, 4, -25, -20, -15, 15, -16, 7, 19, -10, 0, -13, -14};
int k = -33;
Solution s = new Solution();
Console.WriteLine(s.MaxNumWays(nums, k));
}
}This JavaScript solution calculates the prefix sums and potential pivots in two separate loops. It first finds the original maximum partition ways and then tests changes to each element to find additional partitions.
Time Complexity: O(n), as it involves two separate linear passes through the array.
Space Complexity: O(1), since no extra data structures are used apart from primitive accumulators.
Approach 3: Prefix Sum + Hash Table
We can preprocess to get the prefix sum array s corresponding to the array nums, where s[i] represents the sum of the array nums[0,...i-1]. Therefore, the sum of all elements in the array is s[n - 1].
If we do not modify the array nums, the condition for the sums of the two subarrays to be equal is that s[n - 1] must be even. If s[n - 1] is even, then we calculate ans = \frac{right[s[n - 1] / 2]}{2}.
If we modify the array nums, we can enumerate each modification position i, change nums[i] to k, then the change in the total sum of the array is d = k - nums[i]. At this time, the sum of the left part of i remains unchanged, so the legal split must satisfy s[i] = s[n - 1] + d - s[i], that is, s[i] = \frac{s[n - 1] + d}{2}. Each prefix sum of the right part has increased by d, so the legal split must satisfy s[i] + d = s[n - 1] + d - (s[i] + d), that is, s[i] = \frac{s[n - 1] - d}{2}. We use hash tables left and right to record the number of times each prefix sum appears in the left and right parts, respectively. Then we can calculate ans = max(ans, left[\frac{s[n - 1] + d}{2}]) + right[\frac{s[n - 1] - d}{2}].
Finally, we return ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
func waysToPartition(nums []int, k int) (ans int) {
n := len(nums)
s := make([]int, n)
s[0] = nums[0]
right := map[int]int{}
for i := range nums[:n-1] {
right[s[i]]++
s[i+1] = s[i] + nums[i+1]
}
if s[n-1]%2 == 0 {
ans = right[s[n-1]/2]
}
left := map[int]int{}
for i, x := range nums {
d := k - x
if (s[n-1]+d)%2 == 0 {
t := left[(s[n-1]+d)/2] + right[(s[n-1]-d)/2]
if ans < t {
ans = t
}
}
left[s[i]]++
right[s[i]]--
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum Calculation | Time Complexity: O(n), where n is the length of the input array, due to a single pass to compute prefix sums and another to adjust with k. |
| Two-Pass Solution with Adjustment | Time Complexity: O(n), as it involves two separate linear passes through the array. |
| Prefix Sum + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Understanding the mechanics of partition sums or when constraints are very small |
| Prefix Sum with Difference Counting | O(n) | O(n) | General optimal solution using prefix sums and hash maps |
| Two-Pass Adjustment with Maps | O(n) | O(n) | Interview-ready implementation that evaluates each modification in constant time |
Frequently asked questions
Is Maximum Number of Ways to Partition an Array easy or hard?
Maximum Number of Ways to Partition an Array is classified as a Hard problem on LeetCode. The challenge comes from recognizing how a single value change shifts partition sums and designing a prefix-difference counting method to evaluate all possibilities efficiently.
Maximum Number of Ways to Partition an Array Python/Java solution
Most implementations follow the same pattern across languages: compute prefix sums, track difference frequencies in hash maps, and simulate replacing each element with k. The logic translates directly to Python dictionaries, Java HashMap, or C++ unordered_map with O(n) complexity.
How to solve Maximum Number of Ways to Partition an Array in O(n)?
First compute the total sum and prefix sums. For each partition index, store the difference between the left and right sums in a hash map. When considering changing nums[i] to k, calculate the delta and use two maps to count partitions that become balanced on the left and right. Each evaluation takes O(1), producing an O(n) algorithm.
What is the best approach for Maximum Number of Ways to Partition an Array?
The best approach uses prefix sums and hash maps to track partition differences. By computing prefix sums once and storing difference frequencies, you can evaluate the effect of replacing each element with k in constant time. This results in an overall O(n) time and O(n) space solution.
Is Maximum Number of Ways to Partition an Array asked at Google/Amazon/Meta?
This problem pattern appears in interviews at large tech companies including Google, Amazon, and Meta. It tests prefix sums, hash map counting, and the ability to transform a brute-force partition problem into a linear-time solution.
What data structure is used in Maximum Number of Ways to Partition an Array?
The core data structures are prefix sums and hash maps (frequency tables). Prefix sums allow constant-time subarray sum checks, while hash maps store counts of partition differences so the algorithm can quickly determine how many partitions become valid after a modification.
What is the time complexity of Maximum Number of Ways to Partition an Array?
The optimal solution runs in O(n) time with O(n) extra space. The algorithm computes prefix sums, stores difference counts in hash maps, and scans the array once more to evaluate the effect of changing each element to k.