Leetcode 2918. Minimum Equal Sum of Two Arrays After Replacing Zeros

Problem Statement

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.

Sample Test Cases

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 <= 10^5
0 <= nums1[i], nums2[i] <= 10^6

Intuition

Our main aim is to minimise the total sum we will get at the very end after replacing all zeros from both arrays.
The minimum will be obtained if we can replace all the zeros with the minimum we are allowed to take. From the constraint, we can see, the minimum is 1. So we can replace all the current zeros of both arrays with 1 and compare the total sum.

Approach

• Count total sum of nums1 and nums2.
• Count the total number of zeros of nums1, nums2 as well.
• Add the number of zeros to the total sum as we are trying to replace it with value 1.
• Check if any of the arrays' total sum is greater, and the number of zeros for the smaller sum array is zero. In that case, we do not have the power to replace any number, as the only allowed replacement is 0. We return -1.
• Else we return the max(totalSum1, totalSum2)

Complexity

• Time complexity:

  O(max(lengthOfNums1, lengthOfNums2))

• Space complexity:

  O(1) as no extra space is used

Code

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return -1l;
        }
        int lengthNums1 = nums1.length;
        int lengthNums2 = nums2.length;
        int iterLength = Math.max(lengthNums1, lengthNums2);
        long totalSumNums1 = 0;
        long totalSumNums2 = 0;
        int totalZeroNums1 = 0;
        int totalZeroNums2 = 0;
        for (int index = 0; index < iterLength; index++) {
            int num1 = index < lengthNums1 ? nums1[index] : -1;
            int num2 = index < lengthNums2 ?nums2[index] : -1;
            if (num1 != -1) {
                totalSumNums1 += num1;
                totalZeroNums1 += num1 == 0 ? 1 : 0;
            }
            if (num2 != -1) {
                totalSumNums2 += num2;
                totalZeroNums2 += num2 == 0 ? 1 : 0;
            }
        }
        long num1TotalReplaced = totalSumNums1 + totalZeroNums1;
        long num2TotalReplaced = totalSumNums2 + totalZeroNums2;
        if (num1TotalReplaced  > num2TotalReplaced  && totalZeroNums2 == 0) {
            return -1;
        }
        if (num2TotalReplaced > num1TotalReplaced && totalZeroNums1 == 0) {
            return -1;
        }
        return Math.max(num1TotalReplaced, num2TotalReplaced);
    }
}