#2025

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Number of Ways to Partition an Array

Determine the maximum number of ways to split an array into equal sums using at most one element change, leveraging prefix sums.

array hash table counting enumeration prefix sum

Problem Statement

Given a 0-indexed integer array nums and an integer k, you can optionally change one element of nums to k. A pivot index is valid if the sum of elements to its left equals the sum of elements to its right. Compute the maximum number of valid pivot indices achievable after at most one change.

Return the maximum number of ways to partition the array into two parts with equal sums, either by leaving the array unchanged or changing one element to k. The solution must efficiently handle large arrays using scanning and hash-based counting.

Examples

Example 1

Input: nums = [2,-1,2], k = 3

Output: 1

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

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

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

Solution Approach

Compute Prefix Sums

Calculate cumulative sums from left to right. For each potential pivot, store the sum of elements before the pivot. This lets you quickly determine the right sum by subtracting from total sum, forming the basis for identifying valid partitions.

Track Pivot Counts with Hash Maps

Use a hash map to count occurrences of each prefix sum. This allows O(1) lookup for how many times changing an element to k would create a new valid pivot. The pattern of array scanning plus hash lookup ensures efficiency when evaluating all positions.

Evaluate Element Changes

For each index, simulate changing nums[i] to k and compute the new effect on prefix sums. Update pivot counts accordingly. Keep track of the maximum pivots achieved, considering both the unchanged array and each single-element modification.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on a single pass to compute prefix sums plus O(n) operations for scanning and hash map updates, giving roughly O(n) overall. Space complexity is O(n) for prefix sums and hash maps to track counts of sums.

What Interviewers Usually Probe

Candidate recognizes the need for prefix sums instead of brute-force pivot checking.
Candidate proposes hash map for counting prefix sums efficiently.
Candidate identifies that changing one element can create additional pivot indices and discusses simulation.

Common Pitfalls or Variants

Common pitfalls

Not considering the unchanged array as a candidate for maximum pivots.
Incorrectly updating prefix sums after a simulated change, leading to wrong pivot counts.
Overlooking negative numbers or zeros affecting partition equality checks.

Follow-up variants

Counting pivots without any allowed element change, purely based on original array sums.
Finding maximum pivots when multiple elements can be changed instead of just one.
Computing partitions where the left sum minus right sum equals a target difference other than zero.

FAQ

What is the core pattern in Maximum Number of Ways to Partition an Array?

The main pattern is array scanning combined with hash map lookups to count prefix sums, identifying valid pivot points efficiently.

Can the array be left unchanged to achieve maximum partitions?

Yes, sometimes the optimal number of pivots is achieved without any change; always compare against the changed-array scenario.

How do negative numbers affect partition calculations?

Negative numbers alter prefix sums, so each potential pivot must consider both positive and negative values to ensure equality of left and right sums.

Is it necessary to try changing every element to k?

Yes, to guarantee maximum pivots, simulate each single-element change, but efficient hash-based counting avoids recomputing all sums repeatedly.

What is a common mistake when implementing this solution?

A frequent error is failing to update the hash map correctly when simulating element changes, which can undercount valid pivot indices.

terminal

Solution

Solution 1: 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]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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

Continue Practicing

#2023 number of pairs of strings with concatenation equal to target #2013 detect squares #3044 most frequent prime