We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Ways to Partition an Array

Number: 2135

Difficulty: Hard

Paid? No

Companies: Google, Salesforce

Problem Description

Given an integer array nums, count the valid ways to partition it into two non-empty parts such that the sum of the left part equals the sum of the right part. You may change at most one element in nums to a given value k (or leave the array unchanged) to maximize the number of such valid partitions.

Key Insights

  • Use the prefix sum technique to quickly compute sums of subarrays.
  • A valid pivot index exists when the prefix sum equals half of the total sum (which must then be even).
  • Changing one element affects all prefix sums from that index onward by a fixed diff = k - original_value.
  • Pre-calculate the valid partition count for the unchanged array.
  • Evaluate the impact of modifying each index by adjusting the prefix sums and count pivots accordingly.
  • Careful handling of indices is required: for pivots before the modified index, no adjustment is made; for pivots at or after the modified index, add the diff.

Space and Time Complexity

Time Complexity: O(n^2) in a naive evaluation per index, but can be optimized to O(n) with precomputation and hash maps. Space Complexity: O(n) due to usage of prefix sums and dictionaries.

Solution

We first compute the total sum of the array. If the total is even, we calculate prefix sums to count the valid partitions without modification (where prefix sum equals total/2). Then for each index, consider changing nums[i] to k. This change introduces a diff = k - nums[i] which affects all subsequent prefix sums. By separating the counting into two cases (pivots before i and pivots at or after i) and comparing their adjusted sums to the target (newTotal/2), we determine the number of valid partitions after the modification. Finally, we return the maximum count from either modifying one element or keeping the array unchanged.

Code Solutions

# Python solution with comments

def waysToPartition(nums, k):
    n = len(nums)
    total = sum(nums)
    
    # Count valid partitions without any modifications
    current = 0
    validPartitions = 0
    for i in range(n - 1):
        current += nums[i]
        if current * 2 == total:
            validPartitions += 1
    maxWays = validPartitions

    # Try modifying each element to k
    for i in range(n):
        diff = k - nums[i]
        newTotal = total + diff
        
        # New total must be even to partition equally
        if newTotal % 2 != 0:
            continue
        
        target = newTotal // 2
        cnt = 0
        cur = 0
        
        # Check each possible pivot for valid partition after modifying nums[i]
        for j in range(n - 1):
            cur += nums[j]
            # For indices from i onward, adjust the prefix sum by diff
            if j >= i:
                if cur + diff == target:
                    cnt += 1
            else:
                if cur == target:
                    cnt += 1
        maxWays = max(maxWays, cnt)
    return maxWays

# Example usage:
print(waysToPartition([2, -1, 2], 3))
← Back to All Questions