LeetCode Problem 2918

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

LeetCode 2918 - Minimum Equal Sum of Two Arrays After Replacing Zeros

Problem Understanding

The problem gives us two integer arrays, nums1 and nums2, where some elements may be 0. Every 0 must be replaced with a strictly positive integer, meaning every replacement must be at least 1. The goal is to make the final sums of both arrays equal while minimizing that common sum.

In simpler terms, we want to transform both arrays so that:

1. Every 0 becomes a positive integer.
2. The total sum of nums1 equals the total sum of nums2.
3. Among all possible equal sums, we choose the smallest one.
4. If no valid equal sum exists, we return -1.

The key detail is that we are not free to change non-zero values. Existing positive integers are fixed, and only zeros can be adjusted. Since replacements must be positive, every zero contributes at least 1 to the final sum.

This observation immediately gives us a minimum achievable sum for each array:

• The fixed non-zero values already contribute to the sum.
• Every zero contributes at least 1.

So for each array:

$$\text{minimum possible sum} = \text{sum of non-zero elements} + \text{number of zeros}$$

The constraints tell us that both arrays can contain up to 10^5 elements. This makes exponential or combinatorial search completely infeasible. We need a linear or near-linear solution.

Several edge cases are important upfront. One tricky situation occurs when one array has no zeros. In that case, its sum becomes fixed and cannot be increased. Another important case is when both arrays already have equal sums but still contain zeros, because replacing zeros with positive integers increases the total. We must carefully determine the minimum achievable equal value. Large numbers are also relevant because array sums can exceed 32-bit integer range, particularly in Go, so int64 should be used.

Approaches

Brute Force Approach

A brute force solution would attempt all possible replacements for every zero and check whether the resulting sums become equal.

For example, if one array contains multiple zeros, we could try assigning different positive integers to each zero, compute the final sum, and compare it against the other array. We would repeat this process across every possible replacement configuration.

This approach is correct because it explores every valid assignment and would eventually discover the minimum equal sum if one exists.

However, this is computationally impossible. Every zero has infinitely many positive replacement possibilities, making the search space effectively unbounded. Even if we artificially capped replacement values, the number of combinations would grow exponentially.

Because n can reach 10^5, brute force is entirely impractical.

Key Insight for an Optimal Solution

The critical insight is that we do not need to determine exact replacement values immediately.

Since every zero must become at least 1, each array has a minimum achievable sum:

$$\text{minSum} = \text{currentSum} + \text{zeroCount}$$

Any additional increase beyond this minimum is always possible, because we can increase any replaced zero arbitrarily.

This means:

• If an array has at least one zero, it can reach any sum greater than or equal to its minimum sum.
• If an array has no zeros, its sum is fixed forever.

The smallest valid equal sum must therefore be:

$$\max(\text{minSum1}, \text{minSum2})$$

But we must verify feasibility.

If one side has no zeros and its fixed sum is smaller than the other side's minimum achievable sum, equality is impossible.

Similarly, if neither side has zeros and sums differ, equality is impossible.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all possible zero replacements
Optimal	O(n + m)	O(1)	Computes minimum achievable sums greedily

Algorithm Walkthrough

1. Compute the total sum of nums1 and count how many zeros it contains.

We store:

• sum1, the sum of all existing values
• zeros1, the number of 0s

2. Compute the same information for nums2.

We store:

• sum2
• zeros2

3. Calculate the minimum achievable sum for each array.

Since every zero must become at least 1:

$$min1 = sum1 + zeros1$$

$$min2 = sum2 + zeros2$$ 4. Handle impossible cases.

If nums1 has no zeros, then its sum is fixed.

If:

$$sum1 < min2$$

then nums1 can never catch up, making equality impossible.

Similarly, if nums2 has no zeros and:

$$sum2 < min1$$

equality is impossible. 5. Return the smallest feasible equal sum.

Since arrays with zeros can always increase their sum as needed, the answer is simply:

$$\max(min1, min2)$$

Why it works

The algorithm relies on a simple invariant: an array containing at least one zero can achieve any sum greater than or equal to its minimum achievable sum.

This is true because we can assign 1 to every zero except one, then use the remaining zero to absorb any additional required difference. Therefore, the only thing that matters is whether both arrays can reach the same target. The smallest valid target is the larger of the two minimum sums, provided no fixed array blocks feasibility.

Python Solution

from typing import List

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

        zeros1 = nums1.count(0)
        zeros2 = nums2.count(0)

        min_sum1 = sum1 + zeros1
        min_sum2 = sum2 + zeros2

        if zeros1 == 0 and sum1 < min_sum2:
            return -1

        if zeros2 == 0 and sum2 < min_sum1:
            return -1

        return max(min_sum1, min_sum2)

The implementation follows the algorithm directly.

We first compute the raw sums and count zeros in both arrays. These values are enough to determine the minimum achievable sum for each side.

Next, we check whether either array is fixed. If an array contains no zeros, its sum cannot change. If that fixed sum is smaller than the other array's minimum possible sum, equality becomes impossible.

Finally, if both sides can reach a common target, we return the larger minimum sum. This guarantees the smallest feasible equal value.

Go Solution

func minSum(nums1 []int, nums2 []int) int64 {
	var sum1, sum2 int64
	zeros1, zeros2 := 0, 0

	for _, num := range nums1 {
		sum1 += int64(num)
		if num == 0 {
			zeros1++
		}
	}

	for _, num := range nums2 {
		sum2 += int64(num)
		if num == 0 {
			zeros2++
		}
	}

	minSum1 := sum1 + int64(zeros1)
	minSum2 := sum2 + int64(zeros2)

	if zeros1 == 0 && sum1 < minSum2 {
		return -1
	}

	if zeros2 == 0 && sum2 < minSum1 {
		return -1
	}

	if minSum1 > minSum2 {
		return minSum1
	}

	return minSum2
}

The Go implementation mirrors the Python logic closely. The main difference is integer handling. Since sums may exceed 32-bit range, we use int64 for all accumulated sums and the return type.

Go slices naturally handle empty-like behavior, although the constraints guarantee at least one element in each array, so no special handling is needed.

Worked Examples

Example 1

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

First, compute sums and zero counts.

Array	Raw Sum	Zeros	Minimum Achievable Sum
nums1	6	2	8
nums2	11	1	12

Since both arrays contain zeros, they can increase beyond their minimum sums.

The smallest common sum must be:

$$\max(8, 12) = 12$$

We can construct it:

Array	Replacement	Final Sum
nums1	[2,4]	12
nums2	[1]	12

Result:

12

Example 2

nums1 = [2,0,2,0]
nums2 = [1,4]

Compute sums and zero counts.

Array	Raw Sum	Zeros	Minimum Achievable Sum
nums1	4	2	6
nums2	5	0	5

nums2 has no zeros, so its sum is permanently fixed at 5.

But nums1 cannot go lower than 6.

Since:

$$5 < 6$$

equality is impossible.

Result:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	We scan both arrays once
Space	O(1)	Only a few variables are used

The algorithm performs a single pass through each array to compute sums and zero counts. No auxiliary data structures proportional to input size are required, so memory usage remains constant.

Test Cases

sol = Solution()

assert sol.minSum([3, 2, 0, 1, 0], [6, 5, 0]) == 12  # example 1
assert sol.minSum([2, 0, 2, 0], [1, 4]) == -1  # example 2

assert sol.minSum([1, 2], [3]) == 3  # already equal without zeros
assert sol.minSum([0], [0]) == 1  # smallest possible replacement
assert sol.minSum([0, 0], [1]) == 2  # zeros must become positive
assert sol.minSum([5], [0, 0]) == 5  # second array can reach fixed sum
assert sol.minSum([0, 0], [5]) == 5  # first array can grow to match
assert sol.minSum([5], [10]) == -1  # fixed unequal sums
assert sol.minSum([1000000, 0], [999999, 0]) == 1000001  # large values
assert sol.minSum([0, 0, 0], [0]) == 3  # many zeros on one side

Test Case Summary

Test	Why
[3,2,0,1,0], [6,5,0]	Validates example 1
[2,0,2,0], [1,4]	Validates impossible example
[1,2], [3]	Already equal without zeros
[0], [0]	Smallest valid input
[0,0], [1]	Minimum positive replacements
[5], [0,0]	Flexible array matching fixed sum
[0,0], [5]	Symmetric feasibility case
[5], [10]	Fixed unequal sums
Large values	Ensures large integer handling
Multiple zeros	Verifies greedy minimum target

Edge Cases

One important edge case occurs when both arrays contain no zeros. In this scenario, neither sum can change. If the sums already match, we simply return that sum. Otherwise, equality is impossible and we return -1. The implementation handles this naturally through the fixed-array feasibility checks.

Another tricky case happens when one array has no zeros but the other does. A naive implementation might incorrectly assume equality is always possible because one side can be adjusted. However, if the fixed sum is smaller than the other array's minimum achievable sum, no solution exists. The feasibility conditions explicitly catch this situation.

A third important case involves arrays consisting entirely of zeros. Since every replacement must be strictly positive, the smallest value for each zero is 1. For example, [0,0,0] has a minimum achievable sum of 3. The implementation correctly computes this using sum + zeroCount.

Finally, large input values can be problematic in languages with fixed-width integers. Since element values may reach 10^6 and array lengths may reach 10^5, sums can exceed standard 32-bit integer capacity. The Go solution uses int64 to safely avoid overflow.