Watch 5 video solutions for Maximum Number of Ways to Partition an Array, a hard level problem involving Array, Hash Table, Counting. This walkthrough by Happy Coding has 4,021 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |