Equal Sum Arrays With Minimum Number of Operations - Solution & Explanation

Problem Overview: You get two integer arrays where every value is between 1 and 6. In one operation you can change any element to any value from 1 to 6. The goal is to make the sums of both arrays equal using the minimum number of operations.

Approach 1: Greedy Difference Reduction (O(n) time, O(1) space)

Start by computing the sum of both arrays. If the sums are already equal, the answer is 0. Otherwise calculate the difference diff = abs(sum1 - sum2). The key observation: each element can contribute a limited change. For example, if an element is 1, it can increase the sum by at most +5; if it is 6, it can decrease the sum by at most -5. Build a frequency count of all possible improvements from both arrays using a simple counting array.

Then greedily apply the largest possible reductions first. For example, operations that reduce the difference by 5 should be used before operations that reduce it by 4, and so on. Because values are restricted to 1..6, the maximum improvement per element is bounded, which allows you to process these gains using a constant-sized counting structure. This approach scans both arrays once and processes improvements in descending order, giving O(n) time and O(1) extra space.

This solution relies heavily on simple frequency counting and greedy selection. If you want to review these concepts, check array, greedy, and counting techniques.

Approach 2: Priority Queue for Maximum Impact Operations (O(n log n) time, O(n) space)

Another strategy explicitly tracks the best operation available at each step. Compute the current difference between the sums. For every element in both arrays, calculate the maximum change it could contribute toward reducing that difference. Push these potential improvements into a max heap.

Repeatedly pop the largest available improvement from the heap and subtract it from the remaining difference. Each pop represents one operation. Continue until the difference becomes zero or negative. The heap ensures you always apply the operation with the largest impact first.

This method is easier to reason about because the greedy choice is handled directly by the heap structure. However, maintaining the priority queue adds a log n factor and requires O(n) additional memory. It’s a good conceptual stepping stone before optimizing to the counting-based greedy solution.

Recommended for interviews: Interviewers usually expect the greedy counting solution. Recognizing that values are limited to 1..6 lets you compress all potential improvements into six buckets and solve the problem in linear time. Demonstrating the heap-based greedy idea first shows solid problem decomposition, but the optimized counting approach shows stronger algorithmic insight.