Minimum Equal Sum of Two Arrays After Replacing Zeros

Med

#2599Time: O(N + M), where N is the length of `nums1` and M is the length of `nums2`. This is because we need to iterate through both arrays once to calculate their sums and zero counts.Space: O(1), as we only use a few variables to store the sums and counts, regardless of the input array sizes.3 companies

Patterns

Greedy

Data structures

Array

Companies

Citadel Twilio Palantir Technologies

Prompt

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 <= nums1.length, nums2.length <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach frames the problem as a search for the smallest possible integer S that can serve as the equal sum for both arrays. We first establish a lower bound for this sum S and then verify if this minimum candidate sum is achievable by both arrays, considering the constraints on replacing zeros.

Algorithm

Create two helper variables, sum1 and zeros1, initialized to zero. Iterate through nums1:
- If an element is 0, increment zeros1.
- Otherwise, add the element's value to sum1.
Similarly, calculate sum2 and zeros2 for the nums2 array.
Calculate the minimum potential sum for each array: potential_sum1 = sum1 + zeros1 and potential_sum2 = sum2 + zeros2. Use long data type for sums to avoid integer overflow.
Determine the target sum, which must be the maximum of the two potential minimums: target_sum = max(potential_sum1, potential_sum2).
Check for impossibility:
- If nums1 has no zeros (zeros1 == 0) and its sum (potential_sum1) is less than the target_sum, it's impossible. Return -1.
- If nums2 has no zeros (zeros2 == 0) and its sum (potential_sum2) is less than the target_sum, it's impossible. Return -1.
If it's possible, the minimum equal sum is target_sum. Return target_sum.

Walkthrough

The core idea is to find the minimum possible sum for each array first. To get the minimum sum for an array, we replace every zero with the smallest possible positive integer, which is 1. Let's say the sum of non-zero elements in nums1 is sum1 and the count of zeros is zeros1. The minimum possible sum for nums1 is s1 = sum1 + zeros1. Similarly, for nums2, the minimum sum is s2 = sum2 + zeros2.

Any final equal sum S must be at least s1 and at least s2. Therefore, the smallest candidate for our answer is S_candidate = max(s1, s2).

Now, we must verify if this S_candidate is actually achievable.

For an array with zeros (e.g., zeros1 > 0), we can achieve any sum greater than or equal to its minimum sum (s1). Since S_candidate >= s1, it's always possible to make the sum of nums1 equal to S_candidate.
For an array with no zeros (e.g., zeros1 == 0), its sum is fixed. It cannot be changed. The sum is sum1 (which equals s1 in this case). It can only equal S_candidate if S_candidate == s1.

This leads to the impossibility condition: if an array has a fixed sum (no zeros) that is smaller than the minimum required sum of the other array, no solution exists. For instance, if s1 < s2 and nums1 has no zeros, it's impossible because the fixed sum s1 can never be raised to match the required sum s2.

Complexity

Time

O(N + M), where N is the length of `nums1` and M is the length of `nums2`. This is because we need to iterate through both arrays once to calculate their sums and zero counts.

Space

O(1), as we only use a few variables to store the sums and counts, regardless of the input array sizes.

Trade-offs

Pros

Correctly solves the problem by identifying the minimum possible equal sum.
The logic is sound and covers all edge cases, such as arrays with no zeros.

Cons

The reasoning is slightly more indirect compared to a direct conditional check.
Framing it as a 'search' might be slightly confusing as the search space collapses to a single candidate.

This approach provides a more direct and streamlined solution. It calculates the minimum possible sum for each array (by replacing zeros with 1s) and then uses a simple set of conditional checks to determine the result. The logic hinges on a key observation: if an array contains zeros, its sum can be increased to any value above its minimum; otherwise, its sum is fixed.

Algorithm

Initialize sum1 = 0, zeros1 = 0, sum2 = 0, zeros2 = 0. Use long for sums.
Iterate through nums1 to compute sum1 and zeros1.
Iterate through nums2 to compute sum2 and zeros2.
Calculate the minimum potential sums: potential_sum1 = sum1 + zeros1 and potential_sum2 = sum2 + zeros2.
If potential_sum1 < potential_sum2:
- If zeros1 == 0, return -1.
- Otherwise, return potential_sum2.
If potential_sum2 < potential_sum1:
- If zeros2 == 0, return -1.
- Otherwise, return potential_sum1.
If they are equal, return potential_sum1.
A more compact way to write the logic is: if (potential_sum1 < potential_sum2 and zeros1 == 0) or (potential_sum2 < potential_sum1 and zeros2 == 0), return -1. Otherwise, return max(potential_sum1, potential_sum2).

Walkthrough

First, we process both arrays to find the sum of their non-zero elements and the count of their zeros. Let these be (sum1, zeros1) and (sum2, zeros2).

The minimum sum we can achieve for nums1 is by replacing all zeros1 zeros with 1s. This gives a minimum sum of potential_sum1 = sum1 + zeros1. Similarly, for nums2, the minimum sum is potential_sum2 = sum2 + zeros2.

We then analyze the relationship between these two minimum potential sums:

Case 1: potential_sum1 == potential_sum2. Both arrays can achieve this sum by replacing all their zeros with 1s. Since this is the minimum possible for both, it is the minimum equal sum. The answer is potential_sum1.
Case 2: potential_sum1 < potential_sum2. To make the sums equal, we must increase the sum of nums1. This is only possible if nums1 has at least one zero (zeros1 > 0), which allows us to replace a zero with a value larger than 1. If zeros1 == 0, the sum of nums1 is fixed and cannot be increased, so it's impossible. If zeros1 > 0, we can raise the sum of nums1 to match potential_sum2. Since potential_sum2 is the minimum possible sum for nums2, the lowest possible equal sum is potential_sum2.
Case 3: potential_sum2 < potential_sum1. This is symmetric to Case 2. We must increase the sum of nums2. This requires nums2 to have at least one zero (zeros2 > 0). If not, it's impossible. Otherwise, the minimum equal sum is potential_sum1.

This case analysis directly yields the answer and the conditions for impossibility.

Complexity

Time

O(N + M), where N and M are the lengths of `nums1` and `nums2` respectively. We perform a single pass on each array.

Space

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

Pros

Highly efficient with a single pass over each array.
The logic is very clear, direct, and easy to implement.
Handles all edge cases correctly and concisely.

Cons

No significant cons; this is the optimal approach for this problem.

Solutions

Solution

1public class Solution {2    public long MinSum(int[] nums1, int[] nums2) {3        long s1 = 0, s2 = 0;4        bool hasZero = false;5        foreach(int x in nums1) {6            hasZero |= x == 0;7            s1 += Math.Max(x, 1);8        }9        foreach(int x in nums2) {10            s2 += Math.Max(x, 1);11        }12        if (s1 > s2) {13            return MinSum(nums2, nums1);14        }15        if (s1 == s2) {16            return s1;17        }18        return hasZero ? s2 : -1;19    }20}

1class Solution {2public3  long minSum(int[] nums1, int[] nums2) {4    long s1 = 0, s2 = 0;5    boolean hasZero = false;6    for (int x : nums1) {7      hasZero |= x == 0;8      s1 += Math.max(x, 1);9    }10    for (int x : nums2) {11      s2 += Math.max(x, 1);12    }13    if (s1 > s2) {14      return minSum(nums2, nums1);15    }16    if (s1 == s2) {17      return s1;18    }19    return hasZero ? s2 : -1;20  }21}

1class Solution {2public:3  long long minSum(vector<int> &nums1, vector<int> &nums2) {4    long long s1 = 0, s2 = 0;5    bool hasZero = false;6    for (int x : nums1) {7      hasZero |= x == 0;8      s1 += max(x, 1);9    }10    for (int x : nums2) {11      s2 += max(x, 1);12    }13    if (s1 > s2) {14      return minSum(nums2, nums1);15    }16    if (s1 == s2) {17      return s1;18    }19    return hasZero ? s2 : -1;20  }21};

1class Solution:2    def minSum(self, nums1: List[int], nums2: List[int]) -> int: s1 = sum(nums1) + nums1 . count(0) s2 = sum(nums2) + nums2 . count(0) if s1 > s2: return self . minSum(nums2, nums1) if s1 == s2: return s1 return - 1 if nums1 . count(0) == 0 else s2

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem