Minimum Equal Sum of Two Arrays After Replacing Zeros - Solution & Explanation

Problem Overview: You get two integer arrays where some elements are 0. Each zero can be replaced with any positive integer. The goal is to choose replacements so both arrays end up with the same total sum, while keeping that common sum as small as possible.

Approach 1: Greedy Replacement Approach (O(n) time, O(1) space)

Scan both arrays once and compute two values for each: the current sum of non‑zero elements and the number of zeros. The smallest value a zero can contribute is 1, so the minimum possible sum for each array becomes sum + zeroCount. The smallest equal sum you can achieve must be at least the larger of these two minimum sums. If one array has no zeros and its fixed sum is smaller than the other array's minimum achievable sum, equality is impossible. Otherwise, the target sum is simply max(minSum1, minSum2). You can always distribute the extra value across zeros in the array with flexibility. This works because increasing any zero replacement only increases the total, so a greedy "minimum first" strategy guarantees the smallest feasible equal sum. Time complexity is O(n) for iterating through both arrays, and space complexity is O(1) since only counters and sums are stored. The logic relies on simple arithmetic and sequential scans over the array.

Approach 2: Dynamic Programming Approach (O(n * S) time, O(S) space)

A more theoretical approach models the problem as constructing reachable sums after replacing zeros. For each array, treat every zero as a variable that can contribute any positive value and compute reachable totals up to a reasonable bound using dynamic programming. After generating possible sums for both arrays, the smallest common value becomes the answer. While correct, this approach is far heavier than necessary because the range of possible sums can grow quickly as replacements increase. The DP state tracks which totals can be formed after processing elements, similar to subset‑sum style transitions. Time complexity grows with the sum bound (O(n * S)) and space is O(S), making it impractical for large inputs compared to the greedy observation.

Recommended for interviews: The greedy strategy is what interviewers expect. The key observation is that every zero must contribute at least 1, which immediately defines the minimum achievable sum of each array. From there, equality requires matching the larger minimum. Showing a brute reasoning first and then simplifying it into the greedy formula demonstrates strong problem‑solving ability and leads to a clean O(n) solution.