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

Minimum Equal Sum of Two Arrays After Replacing Zeros

Number: 3171

Difficulty: Medium

Paid? No

Companies: Citadel, Palantir Technologies, Twilio

Problem Description

You are given two arrays nums1 and nums2 consisting of positive integers and possibly zeros. You must replace all the zeros in both arrays with strictly positive integers so that after replacement, the sum of the elements in both arrays is equal. Return the minimum equal sum you can obtain after replacements, or -1 if it is impossible.

Key Insights

  • The non-zero elements in each array are fixed; only the zeros can be replaced.
  • Since each replacement must be a strictly positive integer, each zero contributes at least 1 to the sum.
  • For an array, the minimum achievable sum is the sum of its non-zero elements plus the number of zeros.
  • If an array has no zeros (i.e. is fixed), its sum cannot change.
  • The valid target equal sum must be at least the maximum of the two arrays’ minimum possible sums.
  • For any array without zeros, the target sum must equal its fixed sum; if not, it is impossible.
  • When one array is fixed and the other has zeros, the fixed array’s sum must be at least the minimum possible sum for the other array.

Space and Time Complexity

Time Complexity: O(n + m) where n and m are the lengths of the two arrays (one pass each to compute sums and zero counts). Space Complexity: O(1) extra space (only a few variables are used for calculations).

Solution

We compute the base (non-zero) sum and count the zeros in each array. For an array with zeros, the minimum achievable sum is (base sum + count of zeros) because each zero must contribute at least 1. For an array with no zeros, the sum is fixed. Let:

  • base1 and z1 be the non-zero sum and zero count for nums1,
  • base2 and z2 for nums2. The minimum sums are:
  • min1 = (z1 > 0 ? base1 + z1 : base1)
  • min2 = (z2 > 0 ? base2 + z2 : base2) The candidate target sum is max(min1, min2), since each array can achieve any sum greater than or equal to its minimum by allocating additional value to its zeros. However, if one array is fixed (i.e. has zero count 0) then the target must equal its fixed sum. Therefore, if candidate does not equal the fixed sum for any array, the answer is impossible (return -1).

Code Solutions

# Function to compute minimum equal sum after replacing zeros.
def minimumEqualSum(nums1, nums2):
    # Calculate the sum of non-zero elements and count zeros for nums1.
    base1 = sum(num for num in nums1)
    zeros1 = nums1.count(0)
    
    # Calculate the sum of non-zero elements and count zeros for nums2.
    base2 = sum(num for num in nums2)
    zeros2 = nums2.count(0)
    
    # Compute the minimum achievable sum for each array.
    min1 = base1 if zeros1 == 0 else base1 + zeros1
    min2 = base2 if zeros2 == 0 else base2 + zeros2
    
    # Candidate target is the maximum of the two minimum sums.
    candidate = max(min1, min2)
    
    # If an array is fixed (has no zeros), it must equal candidate.
    if zeros1 == 0 and candidate != base1:
        return -1
    if zeros2 == 0 and candidate != base2:
        return -1
    
    # Otherwise, candidate is the minimum equal sum possible.
    return candidate

# Example usage:
print(minimumEqualSum([3,2,0,1,0], [6,5,0]))  # Expected output: 12
print(minimumEqualSum([2,0,2,0], [1,4]))        # Expected output: -1
← Back to All Questions