Problem of The Day: Minimum Equal Sum of Two Arrays After Replacing Zeros

Problem Statement

leetcode problem link

Intuition

We are given two integer arrays, nums1 and nums2, which may contain zeros. The goal is to make the sums of both arrays equal, or determine it’s not possible. We are allowed to replace any zero with any positive integer, but to minimize the final sum, we should always replace zeros with the smallest possible value: 1.

Why Replace 0 with 1

Zeros represent flexible values that can be changed to any positive number. Since our goal is to minimize the final sum, we replace each 0 with the smallest valid value, which is 1. This strategy gives us the minimum possible sum for the array and allows us to determine if it’s even possible to match the sums between the two arrays.

Why It’s Impossible Without Any Zeros

If one array has a smaller total sum and contains no zeros, it’s impossible to increase its sum to match the other array because:

• We are not allowed to modify non-zero values.
• The only way to increase an array’s sum is by replacing zeros with larger numbers.
• So, if there are no zeros to replace, we have no control over that array’s total — it’s fixed.

Hence, when the smaller-sum array has no zeros, we cannot make the two arrays equal in sum, and the function must return -1.

Approach

1. Clone nums1 and nums2 to avoid modifying the input.
2. Replace every 0 in the clones with 1.
3. Compute the sum of the modified arrays.
4. If one sum is smaller and the original array has no zeros, it’s impossible to match — return -1.
5. Otherwise, return the larger of the two sums, since that’s the minimal total where both arrays can be equal.

Complexity

• Time complexity:
  \(O(n + m)\) — we iterate over both arrays once.

• Space complexity:
  \(O(n + m)\) — we create clones of both arrays.

Code

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        clone_nums1 = nums1[:]
        clone_nums2 = nums2[:]
        for i in range(len(clone_nums1)):
            if clone_nums1[i] == 0:
                clone_nums1[i] = 1

        for i in range(len(clone_nums2)):
            if clone_nums2[i] == 0:
                clone_nums2[i] = 1

        sum1 = sum(clone_nums1)
        sum2 = sum(clone_nums2)
        if sum1 < sum2 and 0 not in nums1:
            return -1
        if sum2 < sum1 and 0 not in nums2:
            return -1

        return max(sum1, sum2)

Editorial

Approach: Classified Discussion

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        sum1 = sum2 = 0
        zero1 = zero2 = 0

        for i in nums1:
            sum1 += i
            if i == 0:
                sum1 += 1
                zero1 += 1

        for i in nums2:
            sum2 += i
            if i == 0:
                sum2 += 1
                zero2 += 1

        if (zero1 == 0 and sum2 > sum1) or (zero2 == 0 and sum1 > sum2):
            return -1

        return max(sum1, sum2)