Jobs

Interviews

Discussions

Minimum Equal Sum of Two Arrays After Replacing Zeros

Medium

Citadel

4 views

Topics:

Arrays

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 <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁶

Try coding it in LeetCode

Minimum Equal Sum of Two Arrays After Replacing Zeros

Medium

Citadel

4 views

Topics:

Arrays

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 <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values within the arrays, and what is the maximum size of each array?
Can the input arrays contain negative numbers?
If it's impossible to make the sums equal after replacing zeros, what should be the return value?
Are we allowed to replace different numbers of zeros in the two arrays, as long as each zero is replaced by the value '1'?
If both arrays are empty, or one array is empty, what should the returned value be?

Brute Force Solution

Approach

The brute force method for this problem is all about trying every possible combination of numbers to replace the zeros in both lists. Then, for each possible combination, we check if the lists have the same total, and if so, whether that total meets the problem requirements.

Here's how the algorithm would work step-by-step:

First, consider the first list. Look at all the zero spots. For each zero spot, imagine it could be a '1', or it could be a '2', or a '3', and so on, until a very large number.
Try every possible combination of numbers for all the zero spots in the first list. So if you have two zero spots, try '1' and '1', then '1' and '2', then '1' and '3', and so on, and then '2' and '1', '2' and '2', etc.
Do the exact same thing for the second list. Try every combination of numbers to fill in the zero spots.
Now, for every pair of combinations (one from the first list, and one from the second list), add up all the numbers in the first list. Then add up all the numbers in the second list.
If the totals of the two lists are equal, remember that total. This is a possible solution.
If the totals are not equal, discard these combinations and move on.
After trying every single possible combination of numbers for the zero spots in both lists, look at all the totals you remembered. Find the smallest total that is possible.
If you didn't find any matching totals after trying everything, then there is no possible solution.

Code Implementation

def minimum_equal_sum_brute_force(first_list, second_list):
    possible_sums = []
    first_zero_indices = [i for i, number in enumerate(first_list) if number == 0]
    second_zero_indices = [i for i, number in enumerate(second_list) if number == 0]

    def generate_combinations(list_to_modify, zero_indices, index, current_combination):
        nonlocal possible_sums
        if index == len(zero_indices):
            modified_list = list_to_modify[:]
            
            list_sum = sum(modified_list)
            return list_sum, modified_list
        else:
            
            list_sum = None
            modified_list = None
            return list_sum, modified_list

    def iterate_replacements(first_list, second_list):
        nonlocal possible_sums
        import itertools
        
        first_zero_indices_count = first_list.count(0)
        second_zero_indices_count = second_list.count(0)

        #Creates all possible combinations from 1 to the sum of the lists
        for first_replacement in itertools.product(range(1, sum(first_list + second_list) +1), repeat = first_zero_indices_count):
          for second_replacement in itertools.product(range(1, sum(first_list + second_list)+1), repeat = second_zero_indices_count):

            first_list_copy = first_list[:]
            second_list_copy = second_list[:]
            
            first_replacement_index = 0
            for i in range(len(first_list_copy)):
              if first_list_copy[i] == 0:
                first_list_copy[i] = first_replacement[first_replacement_index]
                first_replacement_index += 1

            second_replacement_index = 0
            for i in range(len(second_list_copy)):
              if second_list_copy[i] == 0:
                second_list_copy[i] = second_replacement[second_replacement_index]
                second_replacement_index += 1

            #Check if list sums are equal
            if sum(first_list_copy) == sum(second_list_copy):
              #Must ensure that all zeros are replaced by at least one.
              if all(number > 0 for number in first_list_copy) and all(number > 0 for number in second_list_copy):

                possible_sums.append(sum(first_list_copy))

    iterate_replacements(first_list, second_list)

    if not possible_sums:
        return -1
    else:
        return min(possible_sums)

Big(O) Analysis

Time Complexity

O(infinity) – Let n1 be the number of zeros in nums1 and n2 be the number of zeros in nums2. For each zero in nums1, we iterate through all possible values from 1 to infinity (as theoretically, each zero could be replaced with any positive number). This results in an infinite number of combinations for nums1. Similarly, we have an infinite number of combinations for nums2. We then compare each combination from nums1 with each combination from nums2, leading to infinite comparisons. Therefore, the time complexity is O(infinity).

Space Complexity

O(1) – The described brute force approach doesn't explicitly use any auxiliary data structures that scale with the input size. Although it explores numerous combinations, it doesn't store all of them simultaneously. The 'remembered' totals are single numerical values, and the algorithm only needs to keep track of the smallest total found so far, requiring constant space regardless of the input arrays' sizes. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to make the sums of the two groups of numbers equal by changing some zeros into other numbers. We want to do this in the simplest way possible. The strategy is to figure out the minimum sum each group can achieve, and then compare them to see if we can reach the same total.

Here's how the algorithm would work step-by-step:

Calculate the initial sum of the numbers in the first group and also count the number of zeros in that group.
Calculate the initial sum of the numbers in the second group and also count the number of zeros in that group.
For each group, imagine replacing all the zeros with the smallest possible positive number, which is one, and add that to the initial sum.
If the smallest possible sums are not equal, determine which group has the smaller minimum sum.
If the minimum sum of one group is smaller than the other group and that group has no zeros, it is impossible to make the sums equal.
Otherwise, the sums can be made equal if the two minimum sums are identical.

Code Implementation

def min_impossible(first_array, second_array):
    first_array_sum = sum(first_array)
    second_array_sum = sum(second_array)

    first_array_zeros = first_array.count(0)
    second_array_zeros = second_array.count(0)

    first_array_min_sum = first_array_sum + first_array_zeros
    second_array_min_sum = second_array_sum + second_array_zeros

    if first_array_min_sum < second_array_min_sum:
        # If first is smaller, check if its possible to equalize
        if first_array_zeros == 0:
            return -1
        else:
            return second_array_min_sum

    elif second_array_min_sum < first_array_min_sum:
        # If second is smaller, check if its possible to equalize
        if second_array_zeros == 0:
            return -1
        else:
            return first_array_min_sum
    else:
        # The minimum sums are equal, so it is possible
        return first_array_min_sum

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through each of the two input arrays once to calculate the initial sum and the count of zeros. These iterations are independent and each takes O(n) time, where n is the length of the input array. Since we perform two such independent iterations, the total time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The algorithm calculates sums and counts of zeros using only a few integer variables. These variables, such as the sums for the two arrays and the counts of zeros, require a constant amount of space, irrespective of the sizes of the input arrays. Therefore, the auxiliary space used is constant and independent of the input size N (where N is the combined length of the two input arrays). The space complexity is O(1).

Edge Cases

Case	How to Handle
Both arrays are empty	Return -1 since no sums can be computed.
One array is empty, the other is not	Return -1 since a sum from the empty array is impossible.
Arrays contain only zeros	The minimum equal sum is achievable; fill all zeros with 1 and check if resulting sums are equal, and return if they are, or return -1 if they are not.
Arrays contain only non-zero positive integers	If the sums of the initial arrays are not equal, it is impossible to make them equal by replacing zeros, so return -1.
Arrays contain a very large number of zeros	Check for potential integer overflows when calculating sums after replacing zeros with the minimum possible values (1).
One array sum can never reach the other array sum, even when replacing all zeros with very large integers.	Detect this case and return -1 early to avoid unnecessary computations.
Integer overflow when calculating the sum of an array.	Use a larger data type (e.g., long) to store the sums to prevent integer overflow during calculations.
One or both arrays contain only zeros, and both are very long.	Since all zero values will be converted to 1, just compare array lengths, and if equal return the value which is the array length; otherwise return -1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values within the arrays, and what is the maximum size of each array?
Can the input arrays contain negative numbers?
If it's impossible to make the sums equal after replacing zeros, what should be the return value?
Are we allowed to replace different numbers of zeros in the two arrays, as long as each zero is replaced by the value '1'?
If both arrays are empty, or one array is empty, what should the returned value be?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider the first list. Look at all the zero spots. For each zero spot, imagine it could be a '1', or it could be a '2', or a '3', and so on, until a very large number.
Try every possible combination of numbers for all the zero spots in the first list. So if you have two zero spots, try '1' and '1', then '1' and '2', then '1' and '3', and so on, and then '2' and '1', '2' and '2', etc.
Do the exact same thing for the second list. Try every combination of numbers to fill in the zero spots.
Now, for every pair of combinations (one from the first list, and one from the second list), add up all the numbers in the first list. Then add up all the numbers in the second list.
If the totals of the two lists are equal, remember that total. This is a possible solution.
If the totals are not equal, discard these combinations and move on.
After trying every single possible combination of numbers for the zero spots in both lists, look at all the totals you remembered. Find the smallest total that is possible.
If you didn't find any matching totals after trying everything, then there is no possible solution.

Code Implementation

def minimum_equal_sum_brute_force(first_list, second_list):
    possible_sums = []
    first_zero_indices = [i for i, number in enumerate(first_list) if number == 0]
    second_zero_indices = [i for i, number in enumerate(second_list) if number == 0]

    def generate_combinations(list_to_modify, zero_indices, index, current_combination):
        nonlocal possible_sums
        if index == len(zero_indices):
            modified_list = list_to_modify[:]
            
            list_sum = sum(modified_list)
            return list_sum, modified_list
        else:
            
            list_sum = None
            modified_list = None
            return list_sum, modified_list

    def iterate_replacements(first_list, second_list):
        nonlocal possible_sums
        import itertools
        
        first_zero_indices_count = first_list.count(0)
        second_zero_indices_count = second_list.count(0)

        #Creates all possible combinations from 1 to the sum of the lists
        for first_replacement in itertools.product(range(1, sum(first_list + second_list) +1), repeat = first_zero_indices_count):
          for second_replacement in itertools.product(range(1, sum(first_list + second_list)+1), repeat = second_zero_indices_count):

            first_list_copy = first_list[:]
            second_list_copy = second_list[:]
            
            first_replacement_index = 0
            for i in range(len(first_list_copy)):
              if first_list_copy[i] == 0:
                first_list_copy[i] = first_replacement[first_replacement_index]
                first_replacement_index += 1

            second_replacement_index = 0
            for i in range(len(second_list_copy)):
              if second_list_copy[i] == 0:
                second_list_copy[i] = second_replacement[second_replacement_index]
                second_replacement_index += 1

            #Check if list sums are equal
            if sum(first_list_copy) == sum(second_list_copy):
              #Must ensure that all zeros are replaced by at least one.
              if all(number > 0 for number in first_list_copy) and all(number > 0 for number in second_list_copy):

                possible_sums.append(sum(first_list_copy))

    iterate_replacements(first_list, second_list)

    if not possible_sums:
        return -1
    else:
        return min(possible_sums)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Calculate the initial sum of the numbers in the first group and also count the number of zeros in that group.
Calculate the initial sum of the numbers in the second group and also count the number of zeros in that group.
For each group, imagine replacing all the zeros with the smallest possible positive number, which is one, and add that to the initial sum.
If the smallest possible sums are not equal, determine which group has the smaller minimum sum.
If the minimum sum of one group is smaller than the other group and that group has no zeros, it is impossible to make the sums equal.
Otherwise, the sums can be made equal if the two minimum sums are identical.

Code Implementation

def min_impossible(first_array, second_array):
    first_array_sum = sum(first_array)
    second_array_sum = sum(second_array)

    first_array_zeros = first_array.count(0)
    second_array_zeros = second_array.count(0)

    first_array_min_sum = first_array_sum + first_array_zeros
    second_array_min_sum = second_array_sum + second_array_zeros

    if first_array_min_sum < second_array_min_sum:
        # If first is smaller, check if its possible to equalize
        if first_array_zeros == 0:
            return -1
        else:
            return second_array_min_sum

    elif second_array_min_sum < first_array_min_sum:
        # If second is smaller, check if its possible to equalize
        if second_array_zeros == 0:
            return -1
        else:
            return first_array_min_sum
    else:
        # The minimum sums are equal, so it is possible
        return first_array_min_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both arrays are empty	Return -1 since no sums can be computed.
One array is empty, the other is not	Return -1 since a sum from the empty array is impossible.
Arrays contain only zeros	The minimum equal sum is achievable; fill all zeros with 1 and check if resulting sums are equal, and return if they are, or return -1 if they are not.
Arrays contain only non-zero positive integers	If the sums of the initial arrays are not equal, it is impossible to make them equal by replacing zeros, so return -1.
Arrays contain a very large number of zeros	Check for potential integer overflows when calculating sums after replacing zeros with the minimum possible values (1).
One array sum can never reach the other array sum, even when replacing all zeros with very large integers.	Detect this case and return -1 early to avoid unnecessary computations.
Integer overflow when calculating the sum of an array.	Use a larger data type (e.g., long) to store the sums to prevent integer overflow during calculations.
One or both arrays contain only zeros, and both are very long.	Since all zero values will be converted to 1, just compare array lengths, and if equal return the value which is the array length; otherwise return -1.