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] <= 105Problem 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.
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.
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.
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.
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.
JavaScript
C#
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.
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.
| 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 | — |
| 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 |
LeetCode 2025. Maximum Number of Ways to Partition an Array • Happy Coding • 4,021 views views
Watch 4 more video solutions →Practice Maximum Number of Ways to Partition an Array with our built-in code editor and test cases.
Practice on FleetCode