#2918

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Equal Sum of Two Arrays After Replacing Zeros

Find the minimum sum where two arrays become equal after replacing all zeros with positive integers using a greedy strategy.

array greedy

Problem Statement

You are given two arrays, nums1 and nums2, containing positive integers and zeros. Your task is to replace every zero with a strictly positive integer so that the sum of both arrays becomes equal. If no replacement sequence can achieve this, return -1.

Return the smallest possible equal sum after performing valid replacements. The arrays can be large, up to 10^5 elements, so an efficient greedy approach is needed. Always ensure that each step maintains the potential to reach equality without overshooting the minimum sum.

Examples

Example 1

Input: nums1 = [3,2,0,1,0], nums2 = [6,5,0]

Output: 12

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

It is impossible to make the sum of both arrays equal.

Constraints

1 <= nums1.length, nums2.length <= 105
0 <= nums1[i], nums2[i] <= 106

Solution Approach

Initialize with minimal replacements

Replace all zeros in both arrays with 1 to compute a starting sum for each array. This guarantees all elements are positive and gives a baseline to compare sums.

Greedy adjustment toward equality

Identify which array has the smaller sum and increment its zeros one by one using a greedy approach until the total sum matches the other array. Always choose the minimal increase that moves toward equality to ensure the sum remains minimal.

Validate impossibility quickly

If after replacing all zeros and applying greedy increments the sums cannot match, return -1 immediately. Arrays without zeros in the smaller-sum array that remain smaller than the other array indicate impossibility, a common failure mode.

Complexity Analysis

Metric	Value
Time	O(n + m)
Space	O(1)

Time complexity is O(n + m) because each element in both arrays is processed once. Space complexity is O(1) since only sum tracking and incremental adjustments are needed, no extra data structures proportional to input size are used.

What Interviewers Usually Probe

They may ask why greedy adjustment ensures minimal sum rather than random replacements.
Expect discussion on edge cases where an array has no zeros but a smaller sum.
They might check if your approach scales for arrays of length 10^5 with high element values.

Common Pitfalls or Variants

Common pitfalls

Replacing zeros with arbitrary large numbers instead of minimal increments, missing the minimal sum.
Ignoring arrays with no zeros, leading to incorrect -1 detection.
Failing to update sums correctly after each greedy increment, causing wrong final sums.

Follow-up variants

Allow zeros to be replaced with any integer including zero, changing the greedy strategy to account for non-positive replacements.
Instead of minimizing sum, maximize sum equality with constraints on maximum allowed element value.
Work with more than two arrays, extending greedy adjustments to multiple sums while maintaining the minimal total sum.

FAQ

What is the main pattern used in Minimum Equal Sum of Two Arrays After Replacing Zeros?

The main pattern is greedy choice plus invariant validation, where zeros are incrementally adjusted to match sums efficiently.

Can we replace zeros with values other than 1 initially?

Yes, but starting with 1 ensures minimal increments and simplifies the greedy approach while preserving the sum invariant.

What happens if one array has no zeros and a smaller sum?

It is impossible to equalize sums, and the function should return -1 immediately.

What is the time complexity of this solution?

The time complexity is O(n + m) since every element is visited once for initialization and potential adjustments.

How does the greedy approach guarantee the minimal equal sum?

By always increasing the smallest-sum array's zeros by the minimal required amount, we prevent overshooting and ensure the sum stays as low as possible.

terminal

Solution

Solution 1: Case Analysis

We consider the case where we treat all $0$s in the array as $1$s, and calculate the sum of the two arrays separately, denoted as $s_1$ and $s_2$. Without loss of generality, we assume that $s_1 \le s_2$.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#2910 minimum number of groups to create a valid assignment #2931 maximum spending after buying items #2900 longest unequal adjacent groups subsequence i