Problem Informations

• Problem Index: 2918
• Problem Link: Minimum Equal Sum of Two Arrays After Replacing Zeros
• Topics: Array, Greedy

Problem Description

You are given two arrays nums1 and nums2 consisting of positive integers.

You have to replace all the 0’s in both arrays with strictly positive integers such that the sum of elements of both arrays becomes equal.

Return the minimum equal sum you can obtain, or -1 if it is impossible.

Example 1:

Input: nums1 = [3,2,0,1,0], nums2 = [6,5,0]
Output: 12
Explanation: We can replace 0’s in the following way:

• Replace the two 0’s in nums1 with the values 2 and 4. The resulting array is nums1 = [3,2,2,1,4].
• Replace the 0 in nums2 with the value 1. The resulting array is nums2 = [6,5,1].
  Both arrays have an equal sum of 12. It can be shown that it is the minimum sum we can obtain.

Example 2:

Input: nums1 = [2,0,2,0], nums2 = [1,4]
Output: -1
Explanation: It is impossible to make the sum of both arrays equal.

Constraints:

• $1 \leq \text{nums1.length, nums2.length} \leq 10^5$
• $0 \leq \text{nums1}[i], \text{nums2}[i] \leq 10^6$

Intuition

The problem involves balancing the sum of two arrays, nums1 and nums2, by replacing all zeros with strictly positive integers. The goal is to achieve an equal sum in both arrays with the minimum possible total value. The challenge arises due to the zeros, which offer flexibility in adjusting the sums but complicate the determination of minimum equal sum.

Approach

To achieve the goal, we need to consider the following steps:

1. Calculate Initial Sums: First, compute the sum of elements in both nums1 and nums2. These initial sums, sum1 and sum2, respectively, will help us understand the disparity between the two arrays.

2. Count Zeros: Determine the number of zeros in both arrays, denoted as zeroCount1 and zeroCount2. These counts are crucial because they represent the degree of freedom we have in manipulating the sums by replacing zeros with positive integers.

3. Check Trivial Cases:

   • If neither array contains zeros and the sums are already equal, the problem is trivially solved, and we return sum1 (or sum2 since they are equal).
   • If there are no zeros in one array but a disparity in sums remains significant enough that the available zeros in the other array cannot equate the sums, the problem is unsolvable, and we return -1. This situation occurs when sum1 < sum2 + zeroCount2 with zeroCount1 == 0 or vice versa.

4. Determine Maximum Contribution: When zeros exist, they can be replaced by positive values to potentially achieve equal sums. The strategy here is to leverage the zeros to add maximum value to the smaller sum, effectively balancing it with the larger sum. The potential new sums can be sum1 + zeroCount1 or sum2 + zeroCount2, taking the maximum of these ensures we return the lowest possible sum that can be reached after adjustments and is equal for both arrays.

5. Return the Result: Using the logic outlined, the solution involves making sure the final sums are equivalent and as small as possible given the constraints of balancing them with available replacements indicated by zero counts.

This structured approach ensures the problem is addressed within specified constraints and edge cases.

Code

C++

class Solution {
public:
    long long minSum(vector<int>& nums1, vector<int>& nums2) {
        // Calculate the sum of elements in nums1 and nums2
        long long sum1 = accumulate(nums1.begin(), nums1.end(), 0LL);
        long long sum2 = accumulate(nums2.begin(), nums2.end(), 0LL);

        // Count the number of zeros in nums1 and nums2
        int zeroCount1 = count(nums1.begin(), nums1.end(), 0);
        int zeroCount2 = count(nums2.begin(), nums2.end(), 0);

        // If there are no zeros and the sums are equal, return the sum; otherwise, return -1
        if (zeroCount1 == 0 && zeroCount2 == 0) {
            return sum1 == sum2 ? sum1 : -1;
        }

        // Check if making the sums equal is impossible when there are zeros
        if ((zeroCount1 == 0 && sum1 < sum2 + zeroCount2) ||
            (zeroCount2 == 0 && sum2 < sum1 + zeroCount1)) {
            return -1;
        }

        // Return the maximum possible sum by replacing zeros with positive integers
        return max(sum1 + zeroCount1, sum2 + zeroCount2);
    }
};

Python

class Solution:
    def minSum(self, nums1, nums2):
        # Calculate the sum of elements in nums1 and nums2
        sum1 = sum(nums1)
        sum2 = sum(nums2)

        # Count the number of zeros in nums1 and nums2
        zeroCount1 = nums1.count(0)
        zeroCount2 = nums2.count(0)

        # If there are no zeros and the sums are equal, return the sum; otherwise, return -1
        if zeroCount1 == 0 and zeroCount2 == 0:
            return sum1 if sum1 == sum2 else -1

        # Check if making the sums equal is impossible when there are zeros
        if (zeroCount1 == 0 and sum1 < sum2 + zeroCount2) or (zeroCount2 == 0 and sum2 < sum1 + zeroCount1):
            return -1

        # Return the maximum possible sum by replacing zeros with positive integers
        return max(sum1 + zeroCount1, sum2 + zeroCount2)

Complexity

• Time complexity: $O(n)$
  The time complexity is determined by the operations accumulate and count, each of which iterates through the entire array once. Given two arrays nums1 and nums2 of lengths $n_1$ and $n_2$ respectively, the time taken is $O(n_1) + O(n_2)$ which simplifies to $O(n)$, where $n = n_1 + n_2$.

• Space complexity: $O(1)$
  The space complexity is $O(1)$ because the algorithm uses a constant amount of additional space regardless of the input size. It only requires a fixed number of variables to store sums and zero counts.