LeetCode 2025 - Maximum Number of Ways to Partition an Array

The problem asks us to count how many valid partition points exist in an array after optionally changing at most one element to a given value k.

leetcodehardarrayhash-tablecountingenumerationprefix-sum

LeetCode Problem 2025

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Counting, Enumeration, Prefix Sum

Solution

Problem Understanding

The problem asks us to count how many valid partition points exist in an array after optionally changing at most one element to a given value k.

A partition is defined by a pivot index pivot such that:

  • 1 <= pivot < n
  • The sum of elements on the left side equals the sum of elements on the right side.

If we define:

  • Left sum = nums[0] + ... + nums[pivot - 1]
  • Right sum = nums[pivot] + ... + nums[n - 1]

then a pivot is valid when:

$$\text{leftSum} = \text{rightSum}$$

We are allowed to either:

  • leave the array unchanged, or
  • choose exactly one index and replace nums[i] with k.

Our goal is to maximize the number of valid pivots after this optional modification.

The array length can be as large as 10^5, which immediately rules out expensive quadratic or cubic solutions. We need an algorithm that is close to linear time.

A key observation is that every partition can be expressed using prefix sums. Let:

$$prefix[i] = nums[0] + nums[1] + ... + nums[i]$$

For a pivot p, the left side sum is prefix[p - 1], and the right side sum is:

$$totalSum - prefix[p - 1]$$

Therefore, a partition is valid when:

$$prefix[p - 1] = totalSum - prefix[p - 1]$$

which simplifies to:

$$2 \times prefix[p - 1] = totalSum$$

This relationship becomes the foundation of the optimal solution.

Several edge cases are important:

  • Arrays that already have many valid partitions without modification.
  • Arrays where changing one element destroys some partitions but creates more elsewhere.
  • Negative numbers, which prevent greedy assumptions.
  • Large values and large array sizes, requiring efficient counting structures.
  • Odd total sums, where no partition can exist unless modification changes parity.

The problem guarantees:

  • 2 <= n <= 10^5
  • Values fit safely within standard integer ranges, though using 64 bit arithmetic is safest in Go.

Approaches

Brute Force Approach

The brute force solution tries every possible modification.

For each index i:

  1. Temporarily replace nums[i] with k.
  2. Recompute all partition sums.
  3. Count how many pivots are valid.
  4. Restore the original value.

We also need to consider the case where no modification is made.

To count partitions for one configuration, we scan all pivots and compare left and right sums.

Since there are n possible modifications and each requires an O(n) scan, the total complexity becomes O(n^2).

With n = 10^5, this is far too slow.

Key Insight

Instead of recomputing all partitions after every modification, we analyze how changing one element affects partition balances.

Suppose:

  • original total sum = total
  • we change nums[i] to k
  • difference introduced =

$$delta = k - nums[i]$$

Then the new total becomes:

$$total + delta$$

Now consider a partition at pivot p.

There are two cases:

  • If p <= i, then the modified element lies on the right side.
  • If p > i, then the modified element lies on the left side.

This means the balance condition changes differently depending on the pivot location relative to i.

Using prefix sums, we can derive:

For pivots before or at i:

$$2 \times prefix[p-1] = total + delta$$

For pivots after i:

$$2 \times prefix[p-1] = total - delta$$

This transforms the problem into counting how many prefix sums satisfy certain target values.

We can maintain these counts efficiently using hash maps.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Recompute all partitions after every modification
Optimal O(n) O(n) Uses prefix sums and hash maps for efficient counting

Algorithm Walkthrough

Step 1, Compute Prefix Sums

We first compute prefix sums for the array.

For each pivot p, the left partition sum is simply prefix[p - 1].

This allows partition checks in constant time.

Step 2, Count Existing Valid Partitions

Without modifying anything, a partition is valid when:

$$2 \times prefix[p-1] = total$$

We count all such pivots as the baseline answer.

Step 3, Prepare Hash Maps

We use two hash maps:

  • rightCounts
  • leftCounts

Initially:

  • rightCounts contains counts of all prefix sums corresponding to pivots.
  • leftCounts is empty.

Each map stores frequencies of prefix sums.

The idea is:

  • leftCounts tracks pivots strictly before the current index.
  • rightCounts tracks pivots at or after the current index.

As we iterate through possible modification indices, pivots migrate from right to left.

Step 4, Try Modifying Each Index

Suppose we modify index i.

Define:

$$delta = k - nums[i]$$

The new total becomes:

$$total + delta$$

Now examine pivot conditions.

For pivots before or at i:

$$2 \times prefix = total + delta$$

Rearranging:

$$prefix = \frac{total + delta}{2}$$

These pivots are counted from leftCounts.

For pivots after i:

$$2 \times prefix = total - delta$$

These pivots are counted from rightCounts.

So the total valid partitions after modifying index i is:

$$leftCounts[targetLeft] + rightCounts[targetRight]$$

where:

$$targetLeft = \frac{total + delta}{2}$$

$$targetRight = \frac{total - delta}{2}$$

We compute this efficiently in constant time using hash map lookups.

Step 5, Update the Maps

After processing index i, we move the pivot corresponding to position i + 1 from rightCounts to leftCounts.

This keeps the maps synchronized with future iterations.

Why it works

The algorithm works because every partition condition depends only on a prefix sum and the total array sum.

Changing one element shifts the total sum by a fixed amount delta. Depending on whether the modified index lies on the left or right side of a pivot, the required prefix sum changes predictably.

By separating pivots into those before and after the modified index, we can count all valid partitions using only hash map frequency lookups.

Every pivot is considered exactly once in the correct category, guaranteeing correctness.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def waysToPartition(self, nums: List[int], k: int) -> int:
        n = len(nums)

        prefix = [0] * n
        prefix[0] = nums[0]

        for i in range(1, n):
            prefix[i] = prefix[i - 1] + nums[i]

        total = prefix[-1]

        # rightCounts stores prefix sums for pivots not yet passed
        rightCounts = defaultdict(int)

        for pivot in range(1, n):
            rightCounts[prefix[pivot - 1]] += 1

        # Count valid partitions without modification
        answer = 0

        if total % 2 == 0:
            answer = rightCounts[total // 2]

        leftCounts = defaultdict(int)

        for i in range(n):
            delta = k - nums[i]

            currentWays = 0

            # Pivots before index i
            leftTarget = total + delta

            if leftTarget % 2 == 0:
                currentWays += leftCounts[leftTarget // 2]

            # Pivots after index i
            rightTarget = total - delta

            if rightTarget % 2 == 0:
                currentWays += rightCounts[rightTarget // 2]

            answer = max(answer, currentWays)

            # Move pivot i+1 from right to left
            if i < n - 1:
                pivotPrefix = prefix[i]

                rightCounts[pivotPrefix] -= 1

                if rightCounts[pivotPrefix] == 0:
                    del rightCounts[pivotPrefix]

                leftCounts[pivotPrefix] += 1

        return answer

The implementation begins by constructing prefix sums so that every partition sum can be computed instantly.

Next, we populate rightCounts with all possible pivot prefix sums. Each pivot corresponds to prefix[pivot - 1].

The baseline answer is computed using the original total sum. If the total is even, then any pivot with prefix sum total // 2 is valid.

The main loop considers changing each element to k.

For each index:

  • delta represents how much the total sum changes.
  • We compute the required prefix sum targets for pivots before and after the modified index.
  • Hash map lookups give the number of valid pivots instantly.

Finally, we shift the current pivot prefix from rightCounts into leftCounts, maintaining the invariant for future iterations.

Go Solution

package main

func waysToPartition(nums []int, k int) int {
	n := len(nums)

	prefix := make([]int64, n)
	prefix[0] = int64(nums[0])

	for i := 1; i < n; i++ {
		prefix[i] = prefix[i-1] + int64(nums[i])
	}

	total := prefix[n-1]

	rightCounts := make(map[int64]int)

	for pivot := 1; pivot < n; pivot++ {
		rightCounts[prefix[pivot-1]]++
	}

	answer := 0

	if total%2 == 0 {
		answer = rightCounts[total/2]
	}

	leftCounts := make(map[int64]int)

	for i := 0; i < n; i++ {
		delta := int64(k - nums[i])

		currentWays := 0

		leftTarget := total + delta

		if leftTarget%2 == 0 {
			currentWays += leftCounts[leftTarget/2]
		}

		rightTarget := total - delta

		if rightTarget%2 == 0 {
			currentWays += rightCounts[rightTarget/2]
		}

		if currentWays > answer {
			answer = currentWays
		}

		if i < n-1 {
			pivotPrefix := prefix[i]

			rightCounts[pivotPrefix]--

			if rightCounts[pivotPrefix] == 0 {
				delete(rightCounts, pivotPrefix)
			}

			leftCounts[pivotPrefix]++
		}
	}

	return answer
}

The Go solution follows the same logic as the Python version, but uses int64 for safety because prefix sums may exceed 32 bit integer limits.

Go maps return zero values automatically for missing keys, which simplifies frequency lookups.

Unlike Python's defaultdict, Go requires explicit map initialization using make.

Worked Examples

Example 1

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

Initial Computation

Index Prefix Sum
0 2
1 1
2 3

Total sum:

$$3$$

Possible pivots:

Pivot Left Prefix
1 2
2 1

Initial rightCounts:

Prefix Count
2 1
1 1

No valid partition initially because total is odd.

Try Changing Index 0

Change 2 -> 3

$$delta = 1$$

New total:

$$4$$

Required targets:

  • Left side target:

$$(3 + 1)/2 = 2$$

  • Right side target:

$$(3 - 1)/2 = 1$$

leftCounts is empty.

rightCounts[1] = 1

So total valid partitions:

$$1$$

Best answer becomes 1.

Example 2

nums = [0,0,0]
k = 1

Prefix sums:

Index Prefix
0 0
1 0
2 0

Total:

$$0$$

All pivots already valid.

rightCounts[0] = 2

Baseline answer:

$$2$$

Any modification reduces the number of valid partitions, so final answer remains 2.

Example 3

nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14]
k = -33

The algorithm evaluates every possible modification in linear time.

When modifying index 2:

-25 -> -33

The resulting array produces four valid partitions, which is the maximum.

The hash maps efficiently count all valid pivots without rescanning the entire array.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass for prefix sums and single pass for evaluation
Space O(n) Hash maps store prefix sum frequencies

The algorithm is linear because every array element and every pivot is processed a constant number of times.

Hash map operations are expected O(1), allowing efficient frequency counting.

The space complexity comes primarily from storing prefix sums and hash map frequencies.

Test Cases

sol = Solution()

# Provided examples
assert sol.waysToPartition([2, -1, 2], 3) == 1  # change creates one partition
assert sol.waysToPartition([0, 0, 0], 1) == 2  # best to leave unchanged
assert sol.waysToPartition(
    [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14],
    -33
) == 4  # complex mixed values

# Minimum size array
assert sol.waysToPartition([1, 1], 1) == 1  # single pivot valid

# No possible partitions
assert sol.waysToPartition([1, 2, 3], 10) == 1  # modification creates partition

# Negative numbers
assert sol.waysToPartition([-1, -1, -1, -1], -1) == 1  # balanced negatives

# Large repeated values
assert sol.waysToPartition([5, 5, 5, 5, 5, 5], 5) == 1  # unchanged best

# Modification improves answer
assert sol.waysToPartition([1, 2, 1, 2, 1], 3) == 2  # modification adds partitions

# Odd total becomes even after modification
assert sol.waysToPartition([1, 1, 1], 2) == 1  # parity changes

# All zeros
assert sol.waysToPartition([0, 0, 0, 0], 100) == 3  # unchanged optimal

# Large negative replacement
assert sol.waysToPartition([10, -10, 10, -10], -100) >= 0  # stress negative delta

Test Summary

Test Why
[2,-1,2] Simple modification creates partition
[0,0,0] Existing partitions already optimal
Large mixed example Validates full algorithm behavior
[1,1] Minimum array size
[1,2,3] Modification required
Negative values Ensures sign handling correctness
Repeated values Tests duplicate prefix sums
[1,2,1,2,1] Modification improves result
Odd total case Tests parity transitions
All zeros Maximum natural partitions

Edge Cases

One important edge case occurs when the array already has the maximum possible number of valid partitions without any modification. A careless implementation might always force a change and accidentally reduce the answer. This implementation explicitly computes the baseline answer before trying modifications, ensuring the unchanged array is considered.

Another tricky case involves odd total sums. A partition requires the total sum to be divisible evenly into two equal halves. If the total is odd, no partition exists initially. However, changing one element may change the parity of the total. The implementation carefully checks divisibility before counting targets, preventing incorrect floor division behavior.

Arrays with many duplicate prefix sums are also important. Multiple pivots can share the same prefix value, especially in arrays containing zeros or repeated patterns. Using frequency maps instead of sets ensures every valid pivot is counted correctly.

A final subtle case involves pivots relative to the modified index. Pivots before the modified element and pivots after it behave differently because the changed value contributes to different sides of the partition. The algorithm handles this by maintaining separate left and right frequency maps, guaranteeing that each pivot uses the correct balance equation.