# Minimum Equal Sum of Two Arrays After Replacing Zeros
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-equal-sum-of-two-arrays-after-replacing-zeros)
Canonical: https://scaleengineer.com/dsa/problems/minimum-equal-sum-of-two-arrays-after-replacing-zeros
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel), [Twilio](https://scaleengineer.com/companies/twilio), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
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 <= 105`
* `0 <= nums1[i], nums2[i] <= 106`

# Approaches
## Search for the Target Sum
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.
**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.
**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.
### Explanation
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`.
### Algorithm
1. 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`.
2. Similarly, calculate `sum2` and `zeros2` for the `nums2` array.
3. 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.
4. Determine the target sum, which must be the maximum of the two potential minimums: `target_sum = max(potential_sum1, potential_sum2)`.
5. 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.
6. If it's possible, the minimum equal sum is `target_sum`. Return `target_sum`.

## Direct Calculation via Case Analysis
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.
**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.
**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.
### Explanation
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.
### Algorithm
1. Initialize `sum1 = 0`, `zeros1 = 0`, `sum2 = 0`, `zeros2 = 0`. Use `long` for sums.
2. Iterate through `nums1` to compute `sum1` and `zeros1`.
3. Iterate through `nums2` to compute `sum2` and `zeros2`.
4. Calculate the minimum potential sums: `potential_sum1 = sum1 + zeros1` and `potential_sum2 = sum2 + zeros2`.
5. If `potential_sum1 < potential_sum2`:
   - If `zeros1 == 0`, return -1.
   - Otherwise, return `potential_sum2`.
6. If `potential_sum2 < potential_sum1`:
   - If `zeros2 == 0`, return -1.
   - Otherwise, return `potential_sum1`.
7. If they are equal, return `potential_sum1`.
8. 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)`.

# Solutions
### CSharp

```csharp
public class Solution {
    public long MinSum(int[] nums1, int[] nums2) {
        long s1 = 0, s2 = 0;
        bool hasZero = false;
        foreach(int x in nums1) {
            hasZero |= x == 0;
            s1 += Math.Max(x, 1);
        }
        foreach(int x in nums2) {
            s2 += Math.Max(x, 1);
        }
        if (s1 > s2) {
            return MinSum(nums2, nums1);
        }
        if (s1 == s2) {
            return s1;
        }
        return hasZero ? s2 : -1;
    }
}
```

### Java

```java
class Solution {
public
  long minSum(int[] nums1, int[] nums2) {
    long s1 = 0, s2 = 0;
    boolean hasZero = false;
    for (int x : nums1) {
      hasZero |= x == 0;
      s1 += Math.max(x, 1);
    }
    for (int x : nums2) {
      s2 += Math.max(x, 1);
    }
    if (s1 > s2) {
      return minSum(nums2, nums1);
    }
    if (s1 == s2) {
      return s1;
    }
    return hasZero ? s2 : -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minSum(vector<int> &nums1, vector<int> &nums2) {
    long long s1 = 0, s2 = 0;
    bool hasZero = false;
    for (int x : nums1) {
      hasZero |= x == 0;
      s1 += max(x, 1);
    }
    for (int x : nums2) {
      s2 += max(x, 1);
    }
    if (s1 > s2) {
      return minSum(nums2, nums1);
    }
    if (s1 == s2) {
      return s1;
    }
    return hasZero ? s2 : -1;
  }
};

```

### Python

```python
class Solution:
    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

```