Equal Sum Arrays With Minimum Number of Operations - Solution & Explanation
Problem Statement
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 <= 1051 <= nums1[i], nums2[i] <= 6
Approach Overview
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.
Approach 1: Greedy Difference Reduction
This approach focuses on greedy operations to reduce the sum difference between nums1 and nums2. Identify which array has the larger sum and attempt to either decrease its elements or increase the elements of the array with the smaller sum. By modifying elements towards their maximum impact (i.e., converting an element to 1 if reducing or to 6 if increasing), you can efficiently approach the sum equilibrium.
This C solution calculates the sum of both arrays. It identifies which array has a larger sum and calculates the difference. Utilizing a greedy approach, it determines the largest possible impact we can make in a single operation and keeps applying operations until the difference reduces to zero or exhaustion of possibilities.
Complexity
Time Complexity: O(N + M) where N and M are the lengths of nums1 and nums2 respectively. This accounts for one pass to calculate sums and sort changes.
Space Complexity: O(1) as additional space usage is minimal.
Approach 2: Priority Queue for Maximum Impact Operations
This approach involves using a max-heap or priority queue to always apply the most impactful operation first. By storing the difference each change can make when applied, the heap helps prioritize maximal changes to reduce operations needed. Consider this applicable when maintaining and retrieving order of largest impacts quickly is more efficient.
This C solution emulates a max-heap using a sorted array to efficiently select the largest changes. This involves computing the possible delta changes for both arrays and consuming them in the order from highest to lowest.
Complexity
Time Complexity: O(N log N + M log M) due to sorting.
Space Complexity: O(N + M) for storing changes.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Difference Reduction | Time Complexity: O(N + M) where N and M are the lengths of |
| Priority Queue for Maximum Impact Operations | Time Complexity: O(N log N + M log M) due to sorting. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Difference Reduction (Counting) | O(n) | O(1) | Optimal solution when values are limited to 1–6 and you want the fastest interview-ready approach |
| Priority Queue Greedy | O(n log n) | O(n) | Useful for understanding greedy impact selection or when implementing a straightforward max-impact strategy |
Video Solution
LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations | Weekly Contest 230 | C++ • Cherry Coding [IIT-G] • 4,325 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Equal Sum Arrays With Minimum Number of Operations easy or hard?
Equal Sum Arrays With Minimum Number of Operations Python/Java solution
How to solve Equal Sum Arrays With Minimum Number of Operations in O(n)?
What is the best approach for Equal Sum Arrays With Minimum Number of Operations?
Is Equal Sum Arrays With Minimum Number of Operations asked at Google/Amazon/Meta?
What data structure is used in Equal Sum Arrays With Minimum Number of Operations?
What is the time complexity of Equal Sum Arrays With Minimum Number of Operations?
Ready to solve this problem?
Practice Equal Sum Arrays With Minimum Number of Operations with our built-in code editor and test cases.
Practice on FleetCode