Skip to main content
Talentd

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

MediumArrayGreedy17 min readAsked at: Amazon, Google, Mathworks +1
Practice this problem

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.

 

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 <= 105
  • 0 <= nums1[i], nums2[i] <= 106

Approach Overview

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.

Approach 1: Greedy Replacement Approach

In this approach, after calculating the current sum of the non-zero elements, we'll need to replace zeros in a way that minimizes the absolute difference in sums of both arrays. The goal is to assign zero replacements such that the sums of both arrays converge to the smallest possible common value.

The C solution increments the sum of arrays while counting the zeros. It checks if the number of zeros is sufficient to adjust the sums to equal each other. If not, it returns -1. Otherwise, it returns the adjusted sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N + M), where N and M are the lengths of the two arrays. Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

Another approach could involve dynamic programming where you maintain differences between sums while iteratively replacing zeros. However, this approach might not be efficient for larger inputs, given the freedom of allocating any positive integer. This theoretical method would track potential sums in a DP table.

The heavy complexity out-weighs the practical need considering the given constraints of input size.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(X*Y) in a worst-case theoretical idea; Space Complexity: could be O(X*Y) for tracking potential sums.

Try this approach in the editor →

Approach 3: Case Analysis

We consider the case where we treat all 0s in the array as 1s, and calculate the sum of the two arrays separately, denoted as s_1 and s_2. Without loss of generality, we assume that s_1 \le s_2.

  • If s_1 = s_2, then the answer is s_1.
  • If s_1 \lt s_2, then there must exist a 0 in nums1 to make the sum of the two arrays equal. In this case, the answer is s_2. Otherwise, it means that it is impossible to make the sum of the two arrays equal, and we return -1.

The time complexity is O(n + m), where n and m are the lengths of the arrays nums1 and nums2, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Replacement Approach

Time Complexity: O(N + M), where N and M are the lengths of the two arrays. Space Complexity: O(1).

Dynamic Programming Approach

Time Complexity: O(X*Y) in a worst-case theoretical idea; Space Complexity: could be O(X*Y) for tracking potential sums.

Case Analysis—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy ReplacementO(n)O(1)Best general solution. Compute sums and zero counts to derive the minimum equal sum directly.
Dynamic ProgrammingO(n * S)O(S)Useful for conceptual exploration of reachable sums, but inefficient for large ranges.

Video Solution

Minimum Equal Sum of Two Arrays After Replacing Zeros | Made Easy | Leetcode 2918 | codestorywithMIK • codestorywithMIK • 6,601 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Equal Sum of Two Arrays After Replacing Zeros easy or hard?
The problem is rated Medium because the implementation is simple but the insight is subtle. Many first attempts try simulation or dynamic programming, while the correct approach relies on recognizing the minimum contribution of each zero and applying a greedy calculation.
Minimum Equal Sum of Two Arrays After Replacing Zeros Python/Java solution
Most implementations follow the same greedy logic: compute sums, count zeros, calculate the minimum achievable sum for each array, and return the maximum of those values if feasible. The code is straightforward in Python, Java, C++, C#, and JavaScript because it only requires loops and arithmetic checks.
How to solve Minimum Equal Sum of Two Arrays After Replacing Zeros in O(n)?
Iterate through both arrays and compute two metrics: total sum of non‑zero elements and number of zeros. The smallest sum each array can reach is sum + zeroCount. If both arrays can increase using zeros, the answer is max(minSum1, minSum2). If one array has no zeros and its sum is smaller than the other array's minimum achievable sum, forming an equal sum is impossible.
What is the best approach for Minimum Equal Sum of Two Arrays After Replacing Zeros?
The greedy approach is the most efficient. Compute the sum of non‑zero elements and the count of zeros in each array. Since every zero must be at least 1, the minimum achievable sum for each array is sum + zeroCount. The smallest equal sum is the maximum of those two values, unless a fixed array without zeros prevents matching it.
Is Minimum Equal Sum of Two Arrays After Replacing Zeros asked at Google/Amazon/Meta?
Problems involving greedy adjustments and array sum constraints frequently appear in interviews at companies like Amazon, Google, and Meta. This problem tests the ability to reason about constraints and derive a mathematical greedy rule instead of simulating replacements.
What data structure is used in Minimum Equal Sum of Two Arrays After Replacing Zeros?
The solution mainly uses arrays and simple counters. No advanced data structures are required. You track sums and zero counts while iterating through each array once.
What is the time complexity of Minimum Equal Sum of Two Arrays After Replacing Zeros?
The optimal greedy solution runs in O(n) time and O(1) extra space. You only scan both arrays once to calculate their sums and the number of zeros. All decisions are then derived from simple arithmetic comparisons.

Ready to solve this problem?

Practice Minimum Equal Sum of Two Arrays After Replacing Zeros with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays