2918: Minimum Equal Sum of Two Arrays After Replacing Zeros

Difficulty: Medium

Topics: Arrays, Greedy Algorithms, Mathematics

Companies: Google, Amazon, Bloomberg

Key Insight: The optimal solution requires calculating base sums and understanding the mathematical relationship between zero counts in both arrays.

Problem Statement

Given two arrays containing positive integers and zeros, replace all zeros with positive integers such that both arrays have equal sums. Return the minimum possible equal sum or -1 if impossible.

Example 1

Input: nums1 = [3,2,0,1,0], nums2 = [6,5,0]
Output: 12
Explanation: Replace zeros with [2,4] in nums1 and [1] in nums2

Example 2

Input: nums1 = [2,0,2,0], nums2 = [1,4]
Output: -1
Explanation: Impossible to balance sums

Problem Link: View on LeetCode ↗

Approach 1: Mathematical Analysis

Calculate base sums and zero counts to determine minimal possible sum.

Algorithm Steps

Calculate sum1 (sum of non-zero elements in nums1) + count of zeros
Calculate sum2 (sum of non-zero elements in nums2) + count of zeros
Determine valid minimal sum based on relationships:
- sum1 < sum2 → Check if sum2 ≤ sum1 + zeros1*inf
- sum2 < sum1 → Check if sum1 ≤ sum2 + zeros2*inf
- If both have zeros → max(base_sum1 + 1, base_sum2 + 1)

Complexity Analysis

Time Complexity	Space Complexity
O(n + m)	O(1)

Optimal Solution

class Solution {
public:
    long long minSum(vector<int>& nums1, vector<int>& nums2) {
        long long sum1 = 0, sum2 = 0;
        int zero1 = 0, zero2 = 0;
        
        for(int num : nums1) {
            if(num == 0) zero1++;
            sum1 += num;
        }
        
        for(int num : nums2) {
            if(num == 0) zero2++;
            sum2 += num;
        }
        
        long long base1 = sum1 + zero1;
        long long base2 = sum2 + zero2;
        
        if(zero1 == 0 && base1 < base2) return -1;
        if(zero2 == 0 && base2 < base1) return -1;
        
        if(zero1 == 0 && zero2 == 0) {
            return sum1 == sum2 ? sum1 : -1;
        }
        
        return max(base1, base2);
    }
};

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        long sum1 = 0, sum2 = 0;
        int zero1 = 0, zero2 = 0;
        
        for(int num : nums1) {
            if(num == 0) zero1++;
            sum1 += num;
        }
        
        for(int num : nums2) {
            if(num == 0) zero2++;
            sum2 += num;
        }
        
        long base1 = sum1 + zero1;
        long base2 = sum2 + zero2;
        
        if(zero1 == 0 && base1 < base2) return -1;
        if(zero2 == 0 && base2 < base1) return -1;
        
        if(zero1 == 0 && zero2 == 0) {
            return sum1 == sum2 ? sum1 : -1;
        }
        
        return Math.max(base1, base2);
    }
}

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        sum1, zero1 = 0, 0
        sum2, zero2 = 0, 0
        
        for num in nums1:
            if num == 0:
                zero1 += 1
            sum1 += num
            
        for num in nums2:
            if num == 0:
                zero2 += 1
            sum2 += num
            
        base1 = sum1 + zero1
        base2 = sum2 + zero2
        
        if zero1 == 0 and base1 < base2:
            return -1
        if zero2 == 0 and base2 < base1:
            return -1
            
        if zero1 == 0 and zero2 == 0:
            return sum1 if sum1 == sum2 else -1
            
        return max(base1, base2)

Implementation Insight: The solution leverages mathematical constraints to determine the minimal possible sum without explicit simulation of replacements.

Key Mathematical Observations

Condition	Calculation	Reasoning
Both arrays have zeros	max(base1, base2)	Each zero adds at least 1, take maximum base
One array has zeros	Check feasibility	Non-zero array's sum must ≤ potential sum
No zeros	Compare sums	Direct equality check required

Critical Edge Case: When one array has no zeros, its sum must be ≤ the other array's potential minimal sum.

Edge Case Analysis

1. All Zeros

nums1 = [0,0], nums2 = [0] → min sum = 3

2. No Zeros

nums1 = [5,5], nums2 = [10] → sum = 10

3. One Array Dominant

nums1 = [10,0], nums2 = [5,5] → min sum = 11

Pitfall Alert: Always check if arrays without zeros have matching sums before other calculations.

Frequently Asked Questions

1. Why add 1 for each zero in base sum?

Each zero must be replaced by at least 1, contributing minimally to the sum.

2. How does the solution handle large numbers?

Uses long integers to prevent overflow, crucial for arrays with 1e5 elements.

3. Why use max(base1, base2)?

Both arrays must reach the same sum, so we need to satisfy the higher base requirement.

4. What if one array has higher non-zero sum but more zeros?

The algorithm automatically selects the maximum base sum to ensure both can reach it.

5. Can zeros be replaced with values greater than 1?

Yes, but the minimal sum requires using the smallest possible replacements (1s).

6. How to verify solution correctness?

Check that: 1) Final sums match, 2) All replacements are positive, 3) No better solution exists.

7. What's the time complexity breakdown?

O(n + m) for array traversal + O(1) calculations. Optimal for large inputs.

8. Why return -1 for some cases?

When constraints make balancing impossible (e.g., fixed sum already too high).

9. How to handle multiple zero replacements?

All zeros must be ≥1, but optimal solution uses exactly 1 for minimal contribution.

10. Practical applications of this problem?

Resource allocation, data balancing, and constraint satisfaction problems.

Final Analysis: This problem teaches essential skills in constraint analysis and mathematical optimization for array manipulation. The solution demonstrates how careful mathematical reasoning can lead to O(n) time algorithms even for seemingly complex problems.