# Maximum Number of Ways to Partition an Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-ways-to-partition-an-array)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-ways-to-partition-an-array
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
---
## 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 < n`
* `nums[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.length`
* `2 <= n <= 105`
* `-105 <= k, nums[i] <= 105`

# Approaches
## Brute Force Simulation
This approach simulates the process directly. It first calculates the number of partitions for the original, unchanged array. Then, it iterates through every possible index `i` from `0` to `n-1`, hypothetically changing `nums[i]` to `k`. For each change, it recalculates the total sum and all prefix sums, and then counts the number of valid partitions. The maximum count found across all these scenarios (including the no-change case) is the answer.
**Time:** O(n^2), where `n` is the length of the array. The outer loop runs `n+1` times (for each element to change, plus the no-change case), and inside, counting partitions takes O(n) time. · **Space:** O(n) if a copy of the array is made in each iteration. If the array is modified in-place and then restored, the space complexity is O(1) besides the input storage.
**Pros:** Simple to understand and implement.; Directly follows the problem statement.
**Cons:** Inefficient due to repeated calculations. For each of the `n` possible changes, it performs O(n) work, leading to a quadratic time complexity which is too slow for the given constraints.
### Explanation
Start by calculating the number of ways to partition the original array. This serves as our initial maximum.
The condition for a valid partition at pivot `p` is `sum(nums[0...p-1]) == sum(nums[p...n-1])`. This can be checked efficiently using prefix sums. Let `S` be the total sum, and `prefix[p]` be the sum of the first `p` elements. The condition is `prefix[p] == S - prefix[p]`, or `2 * prefix[p] == S`.
We can pre-calculate all prefix sums of the original array in O(n) time.
Then, loop through each index `i` from `0` to `n-1`. For each `i`, consider changing `nums[i]` to `k`.
Inside this loop, create a temporary modified array.
Recalculate the prefix sums and the total sum for this modified array.
Count the number of valid partitions for the modified array by iterating through all possible pivots `p` from `1` to `n-1` and checking the partition condition.
Keep track of the maximum number of partitions found so far.
After checking all possible single-element changes, the maximum value recorded is the result.
```java
class Solution {
    private int countPartitions(int[] arr) {
        int n = arr.length;
        long totalSum = 0;
        for (int x : arr) {
            totalSum += x;
        }

        if (totalSum % 2 != 0 && n > 0) {
            // Optimization: if total sum is odd, no integer prefix sum can be half of it.
            // But wait, prefix sums can be non-integers if array has non-integers. Here they are integers.
            // The logic `currentPrefixSum * 2 == totalSum` handles this correctly anyway.
        }

        long currentPrefixSum = 0;
        int count = 0;
        // Pivot p is between index p-1 and p. 1 <= p < n.
        for (int p = 1; p < n; p++) {
            currentPrefixSum += arr[p - 1];
            if (currentPrefixSum * 2 == totalSum) {
                count++;
            }
        }
        return count;
    }

    public int maxWaysToPartition(int[] nums, int k) {
        int n = nums.length;

        // Case 1: No change
        int maxPartitions = countPartitions(nums);

        // Case 2: Change one element
        for (int i = 0; i < n; i++) {
            int originalValue = nums[i];
            nums[i] = k; // Modify the array
            maxPartitions = Math.max(maxPartitions, countPartitions(nums));
            nums[i] = originalValue; // Backtrack
        }

        return maxPartitions;
    }
}
```
### Algorithm
- Define a helper function `countPartitions(array)` that takes an array, calculates its total sum and prefix sums, and returns the number of valid partitions. This takes O(n) time.
- Calculate the initial number of partitions for the unchanged `nums` array using the helper function. Store this as `max_partitions`.
- Iterate through each index `i` from `0` to `n-1`.
- In each iteration, create a temporary copy of `nums`, change the element at index `i` to `k`.
- Call `countPartitions` on the temporary array.
- Update `max_partitions = max(max_partitions, new_count)`.
- Return `max_partitions`.

## Optimized Approach with Prefix Sums and Hash Maps
This approach avoids the O(n^2) complexity by precomputing information and using hash maps to perform lookups in constant time on average. Instead of re-calculating for each change, we analyze how changing a single element `nums[i]` affects the partition condition. The key insight is that a change at index `i` has a different effect on pivots before `i` versus pivots after `i`. We can iterate through all possible change locations `i` and, for each, quickly query the number of pivots that would become valid.
**Time:** O(n). Calculating prefix sums takes O(n). Populating the initial hash map takes O(n). The main loop runs `n` times, and each operation inside (map lookups and updates) takes O(1) on average. · **Space:** O(n). We need O(n) space for the prefix sum array and O(n) for the hash maps in the worst case where all prefix sums are distinct.
**Pros:** Highly efficient with linear time complexity.; Avoids redundant computations by using hash maps for quick lookups.
**Cons:** More complex to reason about and implement correctly compared to the brute-force approach.; Requires careful handling of indices and map updates.
### Explanation
Let `S` be the total sum of the original array and `prefix[p]` be the sum of elements `nums[0...p-1]`. A partition at pivot `p` is valid if `2 * prefix[p] == S`.
If we change `nums[i]` to `k`, the change in value is `diff = k - nums[i]`. The new total sum is `S' = S + diff`.
The partition condition `2 * new_prefix[p] == S'` is affected differently based on `p`'s relation to `i`:
- For a pivot `p <= i`, the prefix sum `prefix[p]` is unchanged. The condition becomes `2 * prefix[p] == S + diff`.
- For a pivot `p > i`, the prefix sum `prefix[p]` increases by `diff`. The condition becomes `2 * (prefix[p] + diff) == S + diff`, which simplifies to `2 * prefix[p] == S - diff`.
We can solve this by iterating through each possible index `i` to change, and for each `i`, counting how many pivots satisfy these two new conditions. To do this counting efficiently, we use two hash maps: `leftCounts` and `rightCounts`.
- `leftCounts` will store the frequencies of `prefix[p]` values for pivots `p <= i`.
- `rightCounts` will store the frequencies of `prefix[p]` values for pivots `p > i`.
We first calculate all prefix sums. Then, we initialize `rightCounts` with frequencies of all `prefix[p]` for `p` from `1` to `n-1`. `leftCounts` is initially empty.
We then iterate `i` from `0` to `n-1`. In each step, we use the maps to find the number of valid partitions for changing `nums[i]`. After that, we update the maps by moving the counts for pivot `p = i+1` from `rightCounts` to `leftCounts` to prepare for the next iteration.
The base case (no change) is also calculated and used to initialize the maximum.
```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxWaysToPartition(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        long totalSum = prefix[n];

        // Case 1: No change
        int noChangeAns = 0;
        for (int p = 1; p < n; p++) {
            if (prefix[p] * 2 == totalSum) {
                noChangeAns++;
            }
        }
        int maxPartitions = noChangeAns;

        // Case 2: Change one element
        Map<Long, Integer> leftCounts = new HashMap<>();
        Map<Long, Integer> rightCounts = new HashMap<>();
        for (int p = 1; p < n; p++) {
            rightCounts.put(prefix[p], rightCounts.getOrDefault(prefix[p], 0) + 1);
        }

        for (int i = 0; i < n; i++) {
            long diff = k - nums[i];
            int currentPartitions = 0;

            // Check pivots p <= i
            long targetLeftSum = totalSum + diff;
            if (targetLeftSum % 2 == 0) {
                currentPartitions += leftCounts.getOrDefault(targetLeftSum / 2, 0);
            }

            // Check pivots p > i
            long targetRightSum = totalSum - diff;
            if (targetRightSum % 2 == 0) {
                currentPartitions += rightCounts.getOrDefault(targetRightSum / 2, 0);
            }

            maxPartitions = Math.max(maxPartitions, currentPartitions);

            // Update maps for the next iteration (i+1)
            // Pivot p = i + 1 moves from right to left
            if (i + 1 < n) {
                long p_val = prefix[i + 1];
                rightCounts.put(p_val, rightCounts.getOrDefault(p_val, 0) - 1);
                if (rightCounts.get(p_val) == 0) {
                    rightCounts.remove(p_val);
                }
                leftCounts.put(p_val, leftCounts.getOrDefault(p_val, 0) + 1);
            }
        }

        return maxPartitions;
    }
}
```
### Algorithm
- Calculate the prefix sums of the `nums` array. Let the array be `prefix`.
- Calculate the number of partitions with no changes (`noChangeAns`) and initialize `maxPartitions = noChangeAns`.
- Initialize a hash map `rightCounts` with the frequencies of `prefix[p]` for all possible pivots `p` (`1 <= p < n`).
- Initialize an empty hash map `leftCounts`.
- Iterate with index `i` from `0` to `n-1` (the index of the element to be changed).
- Inside the loop, calculate `diff = k - nums[i]`.
- Calculate the number of new partitions:
  - Count pivots `p <= i` satisfying `2 * prefix[p] == totalSum + diff` by looking up `(totalSum + diff) / 2` in `leftCounts`.
  - Count pivots `p > i` satisfying `2 * prefix[p] == totalSum - diff` by looking up `(totalSum - diff) / 2` in `rightCounts`.
- Update `maxPartitions` with the sum of these two counts if it's greater.
- Prepare for the next iteration by moving the count for `prefix[i+1]` from `rightCounts` to `leftCounts`.
- Return `maxPartitions`.

# Solutions
### Java

```java
class Solution {
public
  int waysToPartition(int[] nums, int k) {
    int n = nums.length;
    int[] s = new int[n];
    s[0] = nums[0];
    Map<Integer, Integer> right = new HashMap<>();
    for (int i = 0; i < n - 1; ++i) {
      right.merge(s[i], 1, Integer : : sum);
      s[i + 1] = s[i] + nums[i + 1];
    }
    int ans = 0;
    if (s[n - 1] % 2 == 0) {
      ans = right.getOrDefault(s[n - 1] / 2, 0);
    }
    Map<Integer, Integer> left = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      int d = k - nums[i];
      if ((s[n - 1] + d) % 2 == 0) {
        int t = left.getOrDefault((s[n - 1] + d) / 2, 0) +
                right.getOrDefault((s[n - 1] - d) / 2, 0);
        ans = Math.max(ans, t);
      }
      left.merge(s[i], 1, Integer : : sum);
      right.merge(s[i], -1, Integer : : sum);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int waysToPartition(vector<int> &nums, int k) {
    int n = nums.size();
    long long s[n];
    s[0] = nums[0];
    unordered_map<long long, int> right;
    for (int i = 0; i < n - 1; ++i) {
      right[s[i]]++;
      s[i + 1] = s[i] + nums[i + 1];
    }
    int ans = 0;
    if (s[n - 1] % 2 == 0) {
      ans = right[s[n - 1] / 2];
    }
    unordered_map<long long, int> left;
    for (int i = 0; i < n; ++i) {
      int d = k - nums[i];
      if ((s[n - 1] + d) % 2 == 0) {
        int t = left[(s[n - 1] + d) / 2] + right[(s[n - 1] - d) / 2];
        ans = max(ans, t);
      }
      left[s[i]]++;
      right[s[i]]--;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def waysToPartition(self, nums: List[int], k: int) -> int: n = len(nums) s = [nums[0]] * n right = defaultdict(int) for i in range(1, n): s[i] = s[i - 1] + nums[i] right[s[i - 1]] += 1 ans = 0 if s[- 1] % 2 == 0: ans = right[s[- 1] // 2] left = defaultdict(int) for v, x in zip(s, nums): d = k - x if (s[- 1] + d) % 2 == 0: t = left[(s[- 1] + d) // 2] + right[(s[- 1] - d) // 2] if ans < t: ans = t left[v] += 1 right[v] -= 1 return ans

```