LC 2025 [H] Maximum Number of Ways to Partition an Array - ALawliet/algorithms GitHub Wiki

For each pivot point, figure out the the difference between left and right sums, and count each difference in a hash map right.

If we do not change anything, our answer will be the count of zero differences.

Now, what happens if we change num[i] to k?

All differences to the left of i will increase by nums[i] - k.
All differences starting from i will decrease by nums[i] - k.
Now, we go left-to-right, move differences from right to left, and track max partitions if we change the current number.

Now is the tricky part, remember our difference is calculated leftSum - rightSum. Now lets say we added the delta to an index that falls into left side of a pivot. That means leftSum will go up by delta, which means to neutralize it rightSum should also have to go up by delta for diff to be 0. But how can we deduce the fact there exists a pivot point on the right of this given index where RightSum is more than leftSum by delta. We can fortunately find that from diff hashmap where count of all differences where it has -delta as key (as diff = leftSum - rightsum and if rightSum > leftSum by delta, it will give us -delta) So now that can give us all differences to neutralize any increase in leftSum, by doing something like this diffFreq.getOrDefault(-delta, 0) Similarly if the delta falls in the right side of the pivot, and since diff is calculated leftSum - rightSum, there must exist a pivot point on the leftDiff HashMap i.e leftFreq in code below where leftSum is greater than rightSum by delta to neutralize the increase in rightSum. We can find that by leftFreq.getOrDefault(delta, 0)

class Solution:
    def waysToPartition(self, nums: List[int], k: int) -> int:
        presum = list(accumulate(nums))
        rightCnt = Counter()
        leftCnt = Counter()
        
        n = len(nums)
        
        # 1st pass we need at least 2 numbers to split pivot, so we iterate 1->n, and use [i-1], to set rightCnt
        for i in range(1, n):
            prefixsums = presum[i-1] # check
            suffixsums = presum[-1] - prefixsums
            diff = prefixsums - suffixsums
            
            rightCnt[diff] += 1 # check
            
        # if don't change any num
        max_partitions = rightCnt[0]
        
        # 2nd pass we try changing every i to k, so we iterate 0->n, and use [i], to set both Cnt
        for i in range(0, n):
            # all sums on the right increase by d, so needs -d to zero it back out
            # all sums on the left need d more to equal the right
            delta = k - nums[i]
            max_partitions = max(max_partitions, leftCnt[+delta] + rightCnt[-delta])
            
            prefixsums = presum[i] # check
            suffixsums = presum[-1] - prefixsums
            diff = prefixsums - suffixsums
            
            # move right into left
            rightCnt[diff] -= 1 # check
            leftCnt[diff] += 1
            
        return max_partitions