LeetCode 1775 - Equal Sum Arrays With Minimum Number of Operations

The problem gives us two integer arrays, nums1 and nums2, where every element is between 1 and 6. In one operation, we may choose any element from either array and change it to any value from 1 to 6.

leetcodemediumarrayhash-tablegreedycounting

LeetCode Problem 1775

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Counting

Solution

Problem Understanding

The problem gives us two integer arrays, nums1 and nums2, where every element is between 1 and 6. In one operation, we may choose any element from either array and change it to any value from 1 to 6.

Our goal is to make the total sum of both arrays equal while using the minimum possible number of operations.

The important detail is that we are allowed to modify values in both arrays, and every operation can completely replace a number with any valid value. This means an element can contribute differently depending on whether we want to increase or decrease the total sum.

For example:

  • Changing 1 to 6 increases the sum by 5
  • Changing 6 to 1 decreases the sum by 5
  • Changing 3 to 5 increases the sum by 2

The output should be the smallest number of operations needed to make the sums equal. If it is impossible, we return -1.

The constraints are large:

  • Array lengths can each be up to 10^5
  • Values are restricted to only 1 through 6

These constraints immediately tell us that exponential search or simulation of all possible modifications is impossible. We need an algorithm close to linear time.

An important observation is that each element has a maximum possible contribution toward reducing the difference between the sums:

  • If we need to increase a sum, an element x can contribute at most 6 - x
  • If we need to decrease a sum, an element x can contribute at most x - 1

Several edge cases are important:

  • The arrays may have very different lengths
  • One array may already have the same sum as the other
  • It may be mathematically impossible to equalize the sums
  • One side may require many small operations instead of a few large ones
  • Arrays can contain only 1s or only 6s, limiting possible changes

A particularly important impossibility condition comes from the value limits. Since every number must remain between 1 and 6, there are hard limits on possible sums.

For an array of length n:

  • Minimum possible sum is n
  • Maximum possible sum is 6n

If the ranges of achievable sums for the two arrays do not overlap, equalization is impossible.

Approaches

Brute Force Approach

A brute force solution would try all possible modifications to elements in both arrays until the sums become equal.

One possible interpretation of brute force is:

  1. Generate every possible modified state
  2. Compute the sums
  3. Track the minimum operations needed

This quickly becomes infeasible because every element has 6 possible values. If the arrays contain n elements total, the search space becomes approximately:

6^n

Even for relatively small arrays, this is astronomically large.

Another less extreme brute force idea would repeatedly test every possible single modification and greedily choose one. However, without a structured strategy, this still becomes expensive because each operation might require scanning many possibilities repeatedly.

The brute force approach is too slow for arrays up to 10^5.

Key Insight for the Optimal Solution

The key insight is that we do not care about the exact final values of the arrays. We only care about reducing the difference between the sums as quickly as possible.

Suppose:

sum(nums1) < sum(nums2)

Then we need to:

  • Increase elements in nums1
  • Decrease elements in nums2

For every element, we can calculate its maximum possible contribution toward reducing the difference.

Examples:

  • In the smaller-sum array:

  • 1 can become 6, contribution 5

  • 2 can become 6, contribution 4

  • In the larger-sum array:

  • 6 can become 1, contribution 5

  • 5 can become 1, contribution 4

Once we compute all possible contributions, the optimal strategy becomes obvious:

Always use the largest available contribution first.

This is a classic greedy strategy. Since every operation has equal cost, namely one operation, choosing the operation that reduces the difference the most is always optimal.

Because values are only between 1 and 6, contributions are limited to 1 through 5, which makes counting extremely efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(6^n) O(6^n) Explores huge numbers of possible states
Optimal O(n) O(1) Greedy selection using contribution counting

Algorithm Walkthrough

  1. Compute the sums of both arrays.

Let:

sum1 = sum(nums1)
sum2 = sum(nums2)

If the sums are already equal, return 0. 2. Ensure one array always represents the smaller sum.

If sum1 > sum2, swap the arrays and sums.

After this step:

sum1 <= sum2

Now we only need to think about increasing nums1 and decreasing nums2. 3. Compute the required difference.

diff = sum2 - sum1

This is how much we still need to eliminate. 4. Calculate all possible contributions.

For every number in nums1, the largest increase possible is:

6 - num

For every number in nums2, the largest decrease possible is:

num - 1

Each contribution tells us how much one operation could reduce the difference. 5. Count contributions by size.

Since contributions can only be 1 through 5, we store counts in a small array.

Example:

gain[5] = number of operations that can reduce diff by 5
gain[4] = number of operations that can reduce diff by 4
  1. Greedily use the largest contributions first.

Start from contribution 5 down to 1.

For each contribution value:

  • Use as many operations as needed
  • Reduce diff
  • Increment operation count

We always prioritize larger contributions because each operation costs the same. 7. Stop once the difference becomes zero or negative.

At that point, we have equalized the sums. 8. If all contributions are exhausted and diff > 0, return -1.

Why it works

The greedy strategy is optimal because every operation has identical cost, namely one operation. Therefore, whenever we can reduce the remaining difference by a larger amount, doing so is always at least as good as using a smaller reduction.

If an optimal solution used a smaller contribution while a larger unused contribution existed, we could replace the smaller one with the larger one and achieve the same or better reduction using no additional operations. Therefore, choosing the largest available contribution first cannot make the solution worse, which proves the correctness of the greedy approach.

Python Solution

from typing import List

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

        if sum1 == sum2:
            return 0

        # Ensure nums1 has the smaller sum
        if sum1 > sum2:
            nums1, nums2 = nums2, nums1
            sum1, sum2 = sum2, sum1

        diff = sum2 - sum1

        # gain[i] = how many operations can reduce diff by i
        gain = [0] * 6

        # Increasing nums1 elements
        for num in nums1:
            gain[6 - num] += 1

        # Decreasing nums2 elements
        for num in nums2:
            gain[num - 1] += 1

        operations = 0

        # Greedily use biggest gains first
        for value in range(5, 0, -1):
            while gain[value] > 0 and diff > 0:
                diff -= value
                gain[value] -= 1
                operations += 1

        return operations if diff <= 0 else -1

The implementation begins by computing the sums of both arrays. If the sums are already equal, the answer is immediately 0.

Next, the code ensures that nums1 always has the smaller sum. This simplifies the rest of the logic because we only need to think about increasing values in nums1 and decreasing values in nums2.

The variable diff stores the remaining difference between the sums.

The gain array is the core optimization. Since every operation can reduce the difference by at most 5, we only need six slots indexed from 0 to 5.

For every value in nums1, the code calculates how much the value could increase:

6 - num

For every value in nums2, the code calculates how much the value could decrease:

num - 1

These possible reductions are counted in gain.

The final loop processes gains from 5 down to 1. This implements the greedy strategy of always using the most powerful operation first.

As soon as diff <= 0, the sums can be made equal, so the algorithm returns the number of operations used.

Go Solution

package main

func minOperations(nums1 []int, nums2 []int) int {
	sum1 := 0
	sum2 := 0

	for _, num := range nums1 {
		sum1 += num
	}

	for _, num := range nums2 {
		sum2 += num
	}

	if sum1 == sum2 {
		return 0
	}

	// Ensure nums1 has the smaller sum
	if sum1 > sum2 {
		nums1, nums2 = nums2, nums1
		sum1, sum2 = sum2, sum1
	}

	diff := sum2 - sum1

	// gain[i] = count of operations reducing diff by i
	gain := make([]int, 6)

	// Increase nums1
	for _, num := range nums1 {
		gain[6-num]++
	}

	// Decrease nums2
	for _, num := range nums2 {
		gain[num-1]++
	}

	operations := 0

	for value := 5; value >= 1; value-- {
		for gain[value] > 0 && diff > 0 {
			diff -= value
			gain[value]--
			operations++
		}
	}

	if diff > 0 {
		return -1
	}

	return operations
}

The Go implementation follows the same logic as the Python solution. Slices are used for the gain frequency array, and range loops simplify iteration over the arrays.

Go does not require any special handling for integer overflow here because the maximum possible sum is:

6 * 10^5

which easily fits within Go's int type.

Unlike Python, Go does not have built in sum functions, so the sums are computed manually with loops.

Worked Examples

Example 1

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

Initial sums:

Array Sum
nums1 21
nums2 10

Since nums1 has the larger sum, swap them.

Smaller Sum Array Larger Sum Array
[1,1,2,2,2,2] [1,2,3,4,5,6]

Now:

diff = 21 - 10 = 11

Possible gains from smaller array:

Value Gain
1 5
1 5
2 4
2 4
2 4
2 4

Possible gains from larger array:

Value Gain
1 0
2 1
3 2
4 3
5 4
6 5

Gain frequencies:

Gain Count
5 3
4 5
3 1
2 1
1 1

Greedy process:

Operation Gain Used Remaining Diff
1 5 6
2 5 1
3 4 -3

Answer:

3

Example 2

nums1 = [1,1,1,1,1,1,1]
nums2 = [6]

Sums:

Array Sum
nums1 7
nums2 6

Swap arrays:

Smaller Larger
[6] [1,1,1,1,1,1,1]

Difference:

diff = 1

Possible gains:

  • 6 -> 1 gives gain 5
  • Every 1 in larger array gives gain 0

Only one useful operation exists.

But after processing all possible changes, the achievable ranges do not overlap correctly because the larger array cannot be reduced enough and the smaller array cannot be increased enough.

The algorithm eventually exhausts all useful gains and returns:

-1

Example 3

nums1 = [6,6]
nums2 = [1]

Sums:

Array Sum
nums1 12
nums2 1

Swap arrays:

Smaller Larger
[1] [6,6]

Difference:

diff = 11

Possible gains:

Operation Gain
1 -> 6 5
6 -> 1 5
6 -> 1 5

Greedy execution:

Operation Gain Used Remaining Diff
1 5 6
2 5 1
3 5 -4

Total operations:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed a constant number of times
Space O(1) The gain array has fixed size 6

The algorithm scans both arrays once to compute sums and once more to compute contribution frequencies. The greedy loop iterates only over gain values from 5 down to 1, which is constant work.

Although the total number of operations may conceptually be large, each possible contribution is processed once through frequency counting, keeping the runtime linear in the total input size.

The extra memory usage is constant because the gain array always contains exactly six entries regardless of input size.

Test Cases

from typing import List

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

        if sum1 == sum2:
            return 0

        if sum1 > sum2:
            nums1, nums2 = nums2, nums1
            sum1, sum2 = sum2, sum1

        diff = sum2 - sum1

        gain = [0] * 6

        for num in nums1:
            gain[6 - num] += 1

        for num in nums2:
            gain[num - 1] += 1

        operations = 0

        for value in range(5, 0, -1):
            while gain[value] > 0 and diff > 0:
                diff -= value
                gain[value] -= 1
                operations += 1

        return operations if diff <= 0 else -1

sol = Solution()

assert sol.minOperations([1,2,3,4,5,6], [1,1,2,2,2,2]) == 3  # provided example
assert sol.minOperations([1,1,1,1,1,1,1], [6]) == -1  # impossible case
assert sol.minOperations([6,6], [1]) == 3  # provided example

assert sol.minOperations([1], [1]) == 0  # already equal
assert sol.minOperations([1], [6]) == 1  # single operation enough
assert sol.minOperations([1,1,1], [6,6,6]) == 3  # maximum gains needed
assert sol.minOperations([5,6,6], [1,1,1]) == 3  # requires multiple decreases
assert sol.minOperations([2,3,4], [2,3,4]) == 0  # identical arrays
assert sol.minOperations([1]*100000, [6]*100000) == 100000  # large stress case
assert sol.minOperations([1,2], [6,6]) == 2  # mixed operations
assert sol.minOperations([6], [1,1,1,1,1,1]) == 1  # one large increase
Test Why
[1,2,3,4,5,6] vs [1,1,2,2,2,2] Validates standard greedy behavior
[1,1,1,1,1,1,1] vs [6] Validates impossible scenario
[6,6] vs [1] Tests repeated maximum reductions
[1] vs [1] Tests already equal sums
[1] vs [6] Tests single-operation adjustment
[1,1,1] vs [6,6,6] Tests multiple maximum-gain operations
[5,6,6] vs [1,1,1] Tests heavy decreasing operations
[2,3,4] vs [2,3,4] Tests equal arrays
Large arrays of 1s and 6s Stress test for performance
[1,2] vs [6,6] Tests mixed contribution sizes
[6] vs [1,1,1,1,1,1] Tests large gain from a single element

Edge Cases

One important edge case occurs when the sums are already equal at the beginning. A careless implementation might continue processing unnecessarily or even produce an incorrect positive answer. The implementation handles this immediately with:

if sum1 == sum2:
    return 0

Another important edge case is when equalization is impossible. This happens when the total achievable ranges of the arrays do not overlap. For example:

nums1 = [1,1,1,1,1,1,1]
nums2 = [6]

Even after all possible changes, the sums can never become equal. The implementation naturally detects this because all possible gains are exhausted while diff remains positive, causing the function to return -1.

A third critical edge case involves extremely unbalanced arrays with very large input sizes. Since the constraints allow arrays up to 10^5 elements, any quadratic solution would time out. The implementation avoids this by using a fixed-size counting array and processing each element only a constant number of times.

Another subtle edge case occurs when many elements contribute zero gain. For example:

nums1 = [6,6,6]
nums2 = [1,1,1]

If we are trying to increase nums1, its elements already equal 6, so they contribute nothing. Similarly, 1s cannot be decreased further. The implementation handles this correctly because zero-gain operations are ignored naturally through the frequency counting process.

Finally, it is important that the algorithm always processes the larger contributions first. If smaller contributions were used too early, the solution might use more operations than necessary. The descending greedy loop guarantees that the minimum number of operations is always found.