Equal Sum Arrays With Minimum Number of Operations

Med

#1625Time: O(N log N), where N is the total number of elements (nums1.length + nums2.length). The dominant step is sorting the list of all possible gains.Space: O(N), where N is the total number of elements (nums1.length + nums2.length). This space is used to store the list of gains.1 company

Patterns

Greedy Counting

Data structures

Array Hash Table

Companies

American Express

Prompt

You are given two arrays of integers nums1 and nums2, possibly of different lengths. The values in the arrays are between 1 and 6, inclusive.

In one operation, you can change any integer's value in any of the arrays to any value between 1 and 6, inclusive.

Return the minimum number of operations required to make the sum of values in nums1 equal to the sum of values in nums2. Return -1 if it is not possible to make the sum of the two arrays equal.

Example 1:

Input: nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
Output: 3
Explanation: You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed.
- Change nums2[0] to 6. nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2].
- Change nums1[5] to 1. nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2].
- Change nums1[2] to 2. nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2].

Example 2:

Input: nums1 = [1,1,1,1,1,1,1], nums2 = [6]
Output: -1
Explanation: There is no way to decrease the sum of nums1 or to increase the sum of nums2 to make them equal.

Example 3:

Input: nums1 = [6,6], nums2 = [1]
Output: 3
Explanation: You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed. 
- Change nums1[0] to 2. nums1 = [2,6], nums2 = [1].
- Change nums1[1] to 2. nums1 = [2,2], nums2 = [1].
- Change nums2[0] to 4. nums1 = [2,2], nums2 = [4].

Constraints:

1 <= nums1.length, nums2.length <= 10⁵
1 <= nums1[i], nums2[i] <= 6

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first calculates the difference between the sums of the two arrays. To minimize this difference with the fewest operations, we should always make the change that provides the largest reduction in the difference. The possible changes are decreasing an element in the larger-sum array to 1, or increasing an element in the smaller-sum array to 6. We can collect all such possible 'gains' (reductions in difference), sort them in descending order, and apply them one by one until the difference is covered.

Algorithm

Check for impossibility: If 6 * nums1.length < nums2.length or 6 * nums2.length < nums1.length, return -1.
Calculate sum1 and sum2. If they are equal, return 0.
To simplify, ensure sum1 is the larger sum. If sum1 < sum2, swap the roles of the two arrays.
Calculate the target difference diff = sum1 - sum2.
Create a list to store all possible gains from one operation.
For each num in the larger-sum array nums1, add a potential gain of num - 1 to the list.
For each num in the smaller-sum array nums2, add a potential gain of 6 - num to the list.
Sort the list of gains in descending order.
Initialize operations = 0.
Iterate through the sorted gains. For each gain:
Subtract the gain from diff.
Increment operations.
If diff is now less than or equal to 0, break the loop.
Return the total operations.

Walkthrough

The core idea is to greedily reduce the difference between the two sums at each step. We first handle the edge case where it's impossible to make the sums equal. This occurs if the maximum possible sum of one array is less than the minimum possible sum of the other. For an array of length n, the sum is in the range [n, 6*n]. Thus, if 6 * n1 < n2 or 6 * n2 < n1, we return -1.

Otherwise, we calculate the sums sum1 and sum2. To simplify the logic, we can ensure sum1 is always the larger sum by swapping the arrays if sum1 < sum2. The difference to eliminate is diff = sum1 - sum2.

To reduce diff in the minimum number of operations, we should always pick the operation that yields the maximum possible reduction. The possible reductions (gains) are:

Changing an element x from nums1 to 1, giving a gain of x - 1.
Changing an element y from nums2 to 6, giving a gain of 6 - y.

We gather all these potential gains into a single list, sort it in descending order, and apply them greedily until diff is reduced to 0 or less. The number of gains applied gives the minimum number of operations.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int minOperations(int[] nums1, int[] nums2) {7        int n1 = nums1.length;8        int n2 = nums2.length;9 10        if (n1 * 6 < n2 || n2 * 6 < n1) {11            return -1;12        }13 14        long sum1 = 0;15        for (int num : nums1) {16            sum1 += num;17        }18        long sum2 = 0;19        for (int num : nums2) {20            sum2 += num;21        }22 23        if (sum1 == sum2) {24            return 0;25        }26 27        if (sum1 < sum2) {28            // Swap to make sure nums1 has the larger sum29            return minOperations(nums2, nums1);30        }31 32        long diff = sum1 - sum2;33        List<Integer> gains = new ArrayList<>();34        for (int num : nums1) {35            gains.add(num - 1);36        }37        for (int num : nums2) {38            gains.add(6 - num);39        }40 41        Collections.sort(gains, Collections.reverseOrder());42 43        int operations = 0;44        for (int gain : gains) {45            diff -= gain;46            operations++;47            if (diff <= 0) {48                break;49            }50        }51        return operations;52    }53}

Complexity

Time

O(N log N), where N is the total number of elements (nums1.length + nums2.length). The dominant step is sorting the list of all possible gains.

Space

O(N), where N is the total number of elements (nums1.length + nums2.length). This space is used to store the list of gains.

Trade-offs

Pros

Conceptually straightforward greedy logic.
Correctly finds the minimum number of operations.

Cons

The sorting step makes it less efficient than possible, with a time complexity of O(N log N).
Requires extra space proportional to the total number of elements to store the gains.

This approach improves upon the simple greedy strategy by leveraging the constraint that all numbers are between 1 and 6. Instead of creating a list of all possible gains and sorting it, we can use a frequency array to count the occurrences of each possible gain value. The possible gains are integers from 0 to 5. By iterating from the largest possible gain (5) down to the smallest (1), we can greedily reduce the sum difference in the most efficient way, thus avoiding the expensive sorting step.

Algorithm

Check for impossibility: If 6 * nums1.length < nums2.length or 6 * nums2.length < nums1.length, return -1.
Calculate sum1 and sum2. If they are equal, return 0.
To simplify, ensure sum1 is the larger sum. If sum1 < sum2, swap the roles of the two arrays (a recursive call with swapped arguments is a clean way to do this).
Calculate the target difference diff = sum1 - sum2.
Create a frequency array counts of size 6. counts[i] will store the number of available operations that yield a gain of i.
Populate counts: For each num in the larger-sum array nums1, increment counts[num - 1]. For each num in the smaller-sum array nums2, increment counts[6 - num].
Initialize operations = 0.
Iterate through possible gains from largest to smallest (from gain = 5 down to 1).
For each gain value, check if it can cover the remaining diff.
If diff <= gain * counts[gain], calculate the minimum operations of this gain value needed (ceil(diff / gain)), add it to the total operations, and return the result.
If not, use all available operations of this gain value. Add counts[gain] to operations and decrease diff by gain * counts[gain].
After the loop, return the total operations.

Walkthrough

This optimized approach avoids sorting by using a counting array, which is possible due to the small, fixed range of values (1-6) in the input arrays. The initial checks for impossibility and sum calculations are the same as the previous approach. We still ensure sum1 >= sum2 to simplify logic.

The key optimization is how we handle the gains. Instead of a list, we use a counts array of size 6, where counts[i] stores the total number of times a gain of value i can be achieved. The possible gains range from 0 to 5.

For an element x in the larger-sum array, changing it to 1 gives a gain of x-1.
For an element y in the smaller-sum array, changing it to 6 gives a gain of 6-y.

We populate the counts array by iterating through both nums1 and nums2 once. Then, to reduce the diff, we iterate from the largest gain g = 5 down to 1. For each g, we use as many of these gains as needed (or available) to reduce diff. This greedy application of the largest available gains first ensures the minimum number of operations without needing to sort.

1class Solution {2    public int minOperations(int[] nums1, int[] nums2) {3        int n1 = nums1.length;4        int n2 = nums2.length;5 6        if (n1 * 6 < n2 || n2 * 6 < n1) {7            return -1;8        }9 10        long sum1 = 0;11        for (int num : nums1) {12            sum1 += num;13        }14        long sum2 = 0;15        for (int num : nums2) {16            sum2 += num;17        }18 19        if (sum1 == sum2) {20            return 0;21        }22 23        if (sum1 < sum2) {24            // Swap to make sure nums1 has the larger sum25            return minOperations(nums2, nums1);26        }27 28        long diff = sum1 - sum2;29        int[] counts = new int[6]; // counts[i] stores frequency of gain i+130        for (int num : nums1) {31            counts[num - 1]++;32        }33        for (int num : nums2) {34            counts[6 - num]++;35        }36 37        int operations = 0;38        for (int gain = 5; gain >= 1; gain--) {39            if (counts[gain] == 0) {40                continue;41            }42            43            int numAvailable = counts[gain];44            45            if (diff <= (long)gain * numAvailable) {46                operations += (int)((diff + gain - 1) / gain); // Ceiling division47                return operations;48            }49            50            diff -= (long)gain * numAvailable;51            operations += numAvailable;52        }53 54        return operations;55    }56}

Complexity

Time

O(N), where N is the total number of elements (nums1.length + nums2.length). We iterate through the arrays once to calculate sums and populate the counts array, and then iterate through the fixed-size counts array. This is linear time.

Space

O(1), as the extra space used for the `counts` array is constant (size 6), regardless of the input array sizes.

Trade-offs

Pros

Highly efficient with linear time complexity.
Uses constant extra space, making it very memory-efficient.
Optimal solution for this problem due to the constraints on element values.

Cons

The logic is slightly more complex than the sorting-based approach as it relies on the specific constraints of the problem.

Solutions

Solution

1class Solution { public int minOperations ( int [] nums1 , int [] nums2 ) { int s1 = Arrays . stream ( nums1 ). sum (); int s2 = Arrays . stream ( nums2 ). sum (); if ( s1 == s2 ) { return 0 ; } if ( s1 > s2 ) { return minOperations ( nums2 , nums1 ); } int d = s2 - s1 ; int [] arr = new int [ nums1 . length + nums2 . length ]; int k = 0 ; for ( int v : nums1 ) { arr [ k ++] = 6 - v ; } for ( int v : nums2 ) { arr [ k ++] = v - 1 ; } Arrays . sort ( arr ); for ( int i = 1 , j = arr . length - 1 ; j >= 0 ; ++ i , -- j ) { d -= arr [ j ]; if ( d <= 0 ) { return i ; } } return - 1 ; } }

1class Solution { public: int minOperations ( vector < int >& nums1 , vector < int >& nums2 ) { int s1 = accumulate ( nums1 . begin (), nums1 . end (), 0 ); int s2 = accumulate ( nums2 . begin (), nums2 . end (), 0 ); if ( s1 == s2 ) return 0 ; if ( s1 > s2 ) return minOperations ( nums2 , nums1 ); int d = s2 - s1 ; int arr [ nums1 . size () + nums2 . size ()]; int k = 0 ; for ( int & v : nums1 ) arr [ k ++ ] = 6 - v ; for ( int & v : nums2 ) arr [ k ++ ] = v - 1 ; sort ( arr , arr + k , greater <> ()); for ( int i = 0 ; i < k ; ++ i ) { d -= arr [ i ]; if ( d <= 0 ) return i + 1 ; } return - 1 ; } };

1class Solution:2    def minOperations(self, nums1: List[int], nums2: List[int]) -> int: s1, s2 = sum(nums1), sum(nums2) if s1 == s2: return 0 if s1 > s2: return self . minOperations(nums2, nums1) arr = [6 - v for v in nums1] + [v - 1 for v in nums2] d = s2 - s1 for i, v in enumerate(sorted(arr, reverse=True), 1): d -= v if d <= 0: return i return - 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem