2025. Partitions Count

Maximum Number of Ways to Partition an Array

An extremely brain-burning problem. I got it wrong on my first eight attempts 😆

Back then, facing an obviously complex problem like problem 2025 with only around a 36% acceptance rate,

I was quite easy to fall into a shotgun approach.

I later learned to hit the brakes, observe calmly, then react.

Default Max Partitions Count

The problem says we can choose to leave every element unchanged.

So first, look at original array of length $n$:

how many indices $i$ with $1 \leq i < n$ satisfy

$\text{sum}(nums[:i]) = \text{sum}(nums[i:])$?

Default value of max partitions count is:

$C = \Sigma_{i = 1}^{n - 1} \mathbf{1}(\text{sum}(nums[:i]) = \text{sum}(nums[i:]))$

Hard Part: Changing One Element

The problem also allows us to pick exactly one index $j$ and replace $nums[j]$ with input $k$.

This means we need to find which $j$ maximizes:

$C' = \max_{j} \Sigma_{i = 1}^{n - 1} \mathbf{1}(\text{sum}(nums'[:i]) = \text{sum}(nums'[i:]))$

where $nums'$ differs from $nums$ only in that $nums'[j] = k$.

The final answer is $\max(C, C')$.

Find C'

Concept of Prefix-Suffix Difference

First, prepare a hash map called rightDiffCounts, and a pivot index pivotIdx. As defined by the problem, pivotIdx must start from 1 and < $n$.

As pivotIdx traverses from 1 to $n - 1$,

compute prefix-suffix difference $D = \text{sum}(nums[:\text{pivotIdx}]) - \text{sum}(nums[\text{pivotIdx}:])$,

and record count of each $D$ in rightDiffCounts.

What is this difference good for? Imagine:

if some index $l$ less than pivotIdx is selected,

$nums[l]$ changes to $k$, and $nums[l] - k = D$,

then $\text{sum}(nums[:\text{pivotIdx}]) - \text{sum}(nums[\text{pivotIdx}:])$ becomes zero!

pivotIdx becomes a valid split point due to this change, and $C'$ increases by 1.

The Symmetric Trap

one more thing to pay attention to:

when some index $l$ has $nums[l]$ changed to $k$,

the valid split points it creates can be to the left or to the right of $l$.

Using only rightDiffCounts (which tracks prefix-suffix differences for split points to the right of $l$) is not enough.

We also need leftDiffCounts to manage differences for split points to the left of $l$.

Traversal Logic for Final Counting

Prefix Perspective

The traversal index $l$, where $0 \leq l < n$,

checks: after changing $nums[l]$ to $k$,

how many split points to the right of $l$ have a prefix-suffix difference of $nums[l] - k$?

The change to $nums[l]$ affects the prefix sum from the perspective of split points to $l$'s right.

Look up $nums[l] - k$ in rightDiffCounts for the count.

Suffix Perspective

By symmetric reasoning, changing $nums[l]$ to $k$

affects the suffix sum from the perspective of potential split points to $l$'s left.

Count how many split points to the left of $l$ have a prefix-suffix difference of $k - nums[l]$.

Look up $k - nums[l]$ in leftDiffCounts for the count.

Number of perfect split points created by changing $nums[l]$ to $k$ is:

$C'_l$ = leftDiffCounts[k - nums[l]] + rightDiffCounts[nums[l] - k]

Compare this with the current best $C$ and update if it's larger.

Note that since we're dealing with prefix and suffix perspectives, the queried differences differ by exactly a sign flip.

Update Both Hash Maps at Each Step

After visiting index $l$, compute $D_l = \text{sum}(nums[:l + 1]) - \text{sum}(nums[l + 1:])$.

Decrement $D_l$'s count in rightDiffCounts.

Increment $D_l$'s count in leftDiffCounts.

Because from the perspective of all indices larger than $l$, $l$ can only be a left split point, never a right one.

C++

#include <unordered_map>
#include <vector>
using namespace std;

int countMaxPartitions(vector<int>& nums, int k) {
    long long totalSum = 0; // Prevents overflow.
    for (const auto& num : nums)
        totalSum += num;

    // Left diff: only consider potential pivot indices at left side.
    // Right diff: only consider potential pivot indices at right side.
    // Map key: diff = prefix sum - suffix sum.
    unordered_map<long long, int> leftDiffCounts, rightDiffCounts;

    // Default to natural value: leave entire array unchanged.
    int maxPartitionWays = 0;

    long long prefixSum = 0;
    for (int pivotIdx = 1; pivotIdx < nums.size(); pivotIdx++) {
        prefixSum += nums[pivotIdx - 1];
        long long suffixSum = totalSum - prefixSum;
        rightDiffCounts[prefixSum - suffixSum]++;

        // Born as a great partition. No need to change.
        if (prefixSum == suffixSum)
            maxPartitionWays++;
    }

    prefixSum = 0; // Reset to let next for loop sweep again.

    for (int idx = 0; idx < nums.size(); idx++) {
        int num = nums[idx];
        prefixSum += num;

        int partitionWays = 0;

        // Potential pivot idx is at the right of current idx.
        partitionWays += rightDiffCounts[num - k];

        // Potential pivot idx is at the left of current idx.
        partitionWays += leftDiffCounts[k - num];

        if (partitionWays > maxPartitionWays)
            maxPartitionWays = partitionWays;

        long long diff = 2 * prefixSum - totalSum; // Prefix - suffix.

        // For future indices, this diff is only available as left side.
        leftDiffCounts[diff]++;
        rightDiffCounts[diff]--;
    }

    return maxPartitionWays;
}

Python

def count_max_partitions(nums: list[int], k: int) -> int:
    # Left diff: only consider potential pivot indices at left side.
    # Right diff: only consider potential pivot indices at right side.
    # Dict key: diff = prefix sum - suffix sum.
    left_diff_counts: dict[int, int] = dict()
    right_diff_counts: dict[int, int] = dict()

    # Default to natural value: leave entire array unchanged.
    max_partition_ways = 0

    total_sum = sum(nums)
    prefix_sum = 0

    for pivot_idx in range(1, len(nums)):
        prefix_sum += nums[pivot_idx - 1]
        suffix_sum = total_sum - prefix_sum

        diff = prefix_sum - suffix_sum

        if diff not in right_diff_counts.keys():
            right_diff_counts[diff] = 0
        right_diff_counts[diff] += 1

        # Born as a great partition. No need to change.
        if prefix_sum == suffix_sum:
            max_partition_ways += 1

    prefix_sum = 0  # Reset to let next for loop sweep again.

    for idx, num in enumerate(nums):
        prefix_sum += num

        partition_ways = 0

        # Potential pivot idx is at the right of current idx.
        partition_ways += right_diff_counts.get(num - k, 0)

        # Potential pivot idx is at the left of current idx.
        partition_ways += left_diff_counts.get(k - num, 0)

        if partition_ways > max_partition_ways:
            max_partition_ways = partition_ways

        diff = 2 * prefix_sum - total_sum  # Prefix - suffix.
        # For future indices, this diff is only available as left side.

        if diff not in left_diff_counts.keys():
            left_diff_counts[diff] = 0
        left_diff_counts[diff] += 1

        if diff in right_diff_counts.keys():
            right_diff_counts[diff] -= 1

    return max_partition_ways

Time complexity $O(n)$, space complexity $O(n)$.

Logic here is genuinely complex. Think it through several times before key insight clicks.