Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Replacing every zero with one gives the smallest possible sum of an array. If an array contains a zero, that replacement can absorb any further increase. Without a zero, the array's sum is fixed. Thus the larger of the two minimum sums is the only candidate needed.

Approach

Scan both arrays, counting zeros and adding one for each zero when computing their minimum achievable sums. If one minimum is smaller but that array has no zero, it cannot catch up to the larger sum, so return -1.

Otherwise return the larger minimum. The array already at that value uses all-one replacements. The other array, when an increase is needed, has at least one zero and can add the entire difference to that replacement. Equal minimum sums are feasible immediately, including when neither array contains a zero.

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        s1, z1 = 0, 0
        s2, z2 = 0, 0

        for x in nums1:
            if x == 0:
                z1 += 1
                s1 += 1
            else:
                s1 += x

        for x in nums2:
            if x == 0:
                z2 += 1
                s2 += 1
            else:
                s2 += x

        if (s1 > s2 and z2 == 0) or (s2 > s1 and z1 == 0):
            return -1
        return max(s1, s2)

Complexity analysis

Let n = nums1.length and m = nums2.length. Time: O(n + m). Auxiliary space: O(1).