Equal Sum Arrays With Minimum Number of Operations solution and explanation
9 more videos on this problem
LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations | Weekly Contest 230 | C++Cherry Coding [IIT-G] · 15:29 · 4K views
LeetCode 1775. Equal Sum Arrays With Minimum Number of OperationsHappy Coding · 12:58 · 3K views
花花酱 LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations - 刷题找工作 EP387Hua Hua · 18:38 · 2K views
1775. Equal Sum Arrays With Minimum Number of Operations (Leetcode Medium)Programming Live with Larry · 35:02 · 614 views
【每日一题】1775. Equal Sum Arrays With Minimum Number of Operations, 3/2/2021Huifeng Guan · 12:31 · 502 views
LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations宰相小甘罗 · 5:11 · 404 views
LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations 中文宰相小甘罗 · 4:31 · 148 views
大壮刷题 - Leetcode 1775. Equal Sum Arrays With Minimum Number of Operations, Medium大壮刷题 · 10:31 · 118 views
Leetcode 1775. Equal Sum Arrays With Minimum Number of Operations (greedy)LetsCode · 19:39 · 111 views
Leetcode 1775. Equal Sum Arrays With Minimum Number of OperationsFearless Learner · 9:40 · 103 views
The problem
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.
class Solution:
def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
sum1, sum2 = sum(nums1), sum(nums2)
if sum1 < sum2:
nums1, nums2 = nums2, nums1
sum1, sum2 = sum2, sum1
delta = sum1 - sum2
if delta == 0:
return 0
freq = [0] * 6
for num in nums1:
freq[num - 1] += 1
for num in nums2:
freq[6 - num] += 1
ops = 0
for i in range(5, 0, -1):
while freq[i] > 0 and delta > 0:
delta -= i
freq[i] -= 1
ops += 1
return ops if delta <= 0 else -1import java.util.*;
class Solution {
public int minOperations(int[] nums1, int[] nums2) {
int sum1 = Arrays.stream(nums1).sum();
int sum2 = Arrays.stream(nums2).sum();
if (sum1 < sum2) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int tempSum = sum1;
sum1 = sum2;
sum2 = tempSum;
}
int delta = sum1 - sum2;
if (delta == 0) return 0;
int ops = 0;
int[] freq = new int[6];
for (int num : nums1) freq[num - 1]++;
for (int num : nums2) freq[6 - num]++;
for (int i = 5; i > 0 && delta > 0; i--) {
while (freq[i] > 0 && delta > 0) {
delta -= i;
freq[i]--;
ops++;
}
}
return delta <= 0 ? ops : -1;
}
}#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
class Solution {
public:
int minOperations(vector<int>& nums1, vector<int>& nums2) {
int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
if (sum1 < sum2) swap(nums1, nums2), swap(sum1, sum2);
int delta = sum1 - sum2;
if (delta == 0) return 0;
vector<int> possibleChanges;
for (int num : nums1) possibleChanges.push_back(num - 1);
for (int num : nums2) possibleChanges.push_back(6 - num);
sort(possibleChanges.rbegin(), possibleChanges.rend());
int ops = 0;
for (int change : possibleChanges) {
delta -= change;
ops++;
if (delta <= 0) return ops;
}
return -1;
}
};var minOperations = function(nums1, nums2) {
const sum1 = nums1.reduce((a, b) => a + b, 0);
const sum2 = nums2.reduce((a, b) => a + b, 0);
if (sum1 < sum2) {
[nums1, nums2] = [nums2, nums1];
[sum1, sum2] = [sum2, sum1];
}
let delta = sum1 - sum2;
if (delta == 0) return 0;
const freq = Array(6).fill(0);
for (let num of nums1) freq[num - 1]++;
for (let num of nums2) freq[6 - num]++;
let ops = 0;
for (let i = 5; i > 0 && delta > 0; i--) {
while (freq[i] > 0 && delta > 0) {
delta -= i;
freq[i]--;
ops++;
}
}
return delta <= 0 ? ops : -1;
};#include <stdio.h>
#include <stdlib.h>
int minOperations(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int sum1 = 0, sum2 = 0;
for (int i = 0; i < nums1Size; ++i) sum1 += nums1[i];
for (int i = 0; i < nums2Size; ++i) sum2 += nums2[i];
if (sum1 < sum2) {
int* temp = nums1;
nums1 = nums2;
nums2 = temp;
int tempSize = nums1Size;
nums1Size = nums2Size;
nums2Size = tempSize;
int tempSum = sum1;
sum1 = sum2;
sum2 = tempSum;
}
int delta = sum1 - sum2;
if (delta == 0) return 0;
int counts[6] = {0};
for (int i = 0; i < nums1Size; ++i) counts[nums1[i] - 1]++;
for (int i = 0; i < nums2Size; ++i) counts[6 - nums2[i]]++;
int ops = 0;
for (int i = 5; i > 0 && delta > 0; --i) {
while (counts[i] > 0 && delta > 0) {
delta -= i;
counts[i]--;
ops++;
}
}
return delta <= 0 ? ops : -1;
}
int main() {
int nums1[] = {1, 2, 3, 4, 5, 6};
int nums2[] = {1, 1, 2, 2, 2, 2};
printf("%d\n", minOperations(nums1, 6, nums2, 6));
return 0;
}using System;
using System.Linq;
public class Solution {
public int MinOperations(int[] nums1, int[] nums2) {
int sum1 = nums1.Sum();
int sum2 = nums2.Sum();
if (sum1 < sum2) {
var tempArr = nums1;
nums1 = nums2;
nums2 = tempArr;
int temp = sum1;
sum1 = sum2;
sum2 = temp;
}
int delta = sum1 - sum2;
if (delta == 0) return 0;
int ops = 0;
int[] freq = new int[6];
foreach (var num in nums1) freq[num - 1]++;
foreach (var num in nums2) freq[6 - num]++;
for (int i = 5; i > 0 && delta > 0; --i) {
while (freq[i] > 0 && delta > 0) {
delta -= i;
freq[i]--;
ops++;
}
}
return delta <= 0 ? ops : -1;
}
}The Python solution leverages the same logical flow with list comprehensions and conditionals available in Python. It utilizes frequency arrays and loops for delta adjustments in a structured manner.
Time Complexity: O(N + M) given array traversals and constant operations
Space Complexity: O(1) as all operations are in place besides fixed-size auxiliary data.
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.
import heapq
class Solution:
def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
sum1, sum2 = sum(nums1), sum(nums2)
if sum1 < sum2:
nums1, nums2 = nums2, nums1
sum1, sum2 = sum2, sum1
delta = sum1 - sum2
if delta == 0:
return 0
max_heap = []
for num in nums1:
heapq.heappush(max_heap, 1 - num)
for num in nums2:
heapq.heappush(max_heap, num - 6)
heapq.heapify(max_heap)
max_heap = [-x for x in max_heap] # Invert values for max-heap simulation
heapq.heapify(max_heap)
ops = 0
while max_heap and delta > 0:
delta += heapq.heappop(max_heap)
ops += 1
return ops if delta <= 0 else -1import java.util.*;
class Solution {
public int minOperations(int[] nums1, int[] nums2) {
int sum1 = Arrays.stream(nums1).sum();
int sum2 = Arrays.stream(nums2).sum();
if (sum1 < sum2) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int tempSum = sum1;
sum1 = sum2;
sum2 = tempSum;
}
int delta = sum1 - sum2;
if (delta == 0) return 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int num : nums1) pq.offer(num - 1);
for (int num : nums2) pq.offer(6 - num);
int ops = 0;
while (!pq.isEmpty() && delta > 0) {
delta -= pq.poll();
ops++;
}
return delta <= 0 ? ops : -1;
}
}#include <vector>
#include <queue>
#include <numeric>
using namespace std;
class Solution {
public:
int minOperations(vector<int>& nums1, vector<int>& nums2) {
int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
if (sum1 < sum2) swap(nums1, nums2), swap(sum1, sum2);
int delta = sum1 - sum2;
if (delta == 0) return 0;
priority_queue<int> pq;
for (int num : nums1) pq.push(num - 1);
for (int num : nums2) pq.push(6 - num);
int ops = 0;
while (!pq.empty() && delta > 0) {
delta -= pq.top();
pq.pop();
ops++;
}
return delta <= 0 ? ops : -1;
}
};var minOperations = function(nums1, nums2) {
const sum1 = nums1.reduce((p, v) => p + v, 0);
const sum2 = nums2.reduce((p, v) => p + v, 0);
if (sum1 < sum2) [nums1, nums2] = [nums2, nums1], [sum1, sum2] = [sum2, sum1];
let delta = sum1 - sum2;
if (delta == 0) return 0;
const changes = [];
for (let num of nums1) changes.push(num - 1);
for (let num of nums2) changes.push(6 - num);
changes.sort((a, b) => b - a); // Sort in descending order
let ops = 0;
for (let change of changes) {
if (delta <= 0) break;
delta -= change;
ops++;
}
return delta <= 0 ? ops : -1;
};// Priority Queue is complex in C; using a simplified solution instead.
#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)b) - (*(int*)a); // Descending order
}
int minOperations(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int sum1 = 0, sum2 = 0;
for (int i = 0; i < nums1Size; ++i) sum1 += nums1[i];
for (int i = 0; i < nums2Size; ++i) sum2 += nums2[i];
if (sum1 < sum2) {
int* temp = nums1;
nums1 = nums2;
nums2 = temp;
int tempSize = nums1Size;
nums1Size = nums2Size;
nums2Size = tempSize;
int tempSum = sum1;
sum1 = sum2;
sum2 = tempSum;
}
int delta = sum1 - sum2;
if (delta == 0) return 0;
int* changes = (int*)malloc((nums1Size + nums2Size) * sizeof(int));
int idx = 0;
for (int i = 0; i < nums1Size; ++i) changes[idx++] = nums1[i] - 1;
for (int i = 0; i < nums2Size; ++i) changes[idx++] = 6 - nums2[i];
qsort(changes, nums1Size + nums2Size, sizeof(int), compare);
int ops = 0;
for (int i = 0; i < nums1Size + nums2Size && delta > 0; i++) {
delta -= changes[i];
ops++;
}
free(changes);
return delta <= 0 ? ops : -1;
}
int main() {
int nums1[] = {1, 2, 3, 4, 5, 6};
int nums2[] = {1, 1, 2, 2, 2, 2};
printf("%d\n", minOperations(nums1, 6, nums2, 6));
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int MinOperations(int[] nums1, int[] nums2) {
int sum1 = nums1.Sum();
int sum2 = nums2.Sum();
if (sum1 < sum2) {
var tempArr = nums1;
nums1 = nums2;
nums2 = tempArr;
int temp = sum1;
sum1 = sum2;
sum2 = temp;
}
int delta = sum1 - sum2;
if (delta == 0) return 0;
PriorityQueue<int, int> pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
foreach (var num in nums1) pq.Enqueue(num - 1, num - 1);
foreach (var num in nums2) pq.Enqueue(6 - num, 6 - num);
int ops = 0;
while (pq.Count > 0 && delta > 0) {
delta -= pq.Dequeue();
ops++;
}
return delta <= 0 ? ops : -1;
}
}The Python solution utilizes the heapq library to manage operations with a max-heap simulation by inverting elements, efficiently identifying maximal reductions to adaptively approach the balance.
Time Complexity: O((N + M) log(N + M)) related to computational priority queue operations.
Space Complexity: O(N + M) given the storage buffer for heap elements.
Approach 3: Default Approach
func minOperations(nums1 []int, nums2 []int) int {
s1, s2 := sum(nums1), sum(nums2)
if s1 == s2 {
return 0
}
if s1 > s2 {
return minOperations(nums2, nums1)
}
d := s2 - s1
arr := []int{}
for _, v := range nums1 {
arr = append(arr, 6-v)
}
for _, v := range nums2 {
arr = append(arr, v-1)
}
sort.Sort(sort.Reverse(sort.IntSlice(arr)))
for i, v := range arr {
d -= v
if d <= 0 {
return i + 1
}
}
return -1
}
func sum(nums []int) (s int) {
for _, v := range nums {
s += v
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Difference Reduction | Time Complexity: O(N + M) given array traversals and constant operations |
| Priority Queue for Maximum Impact Operations | Time Complexity: O((N + M) log(N + M)) related to computational priority queue operations. |
| Default Approach | – |
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 |
Frequently asked questions
Is Equal Sum Arrays With Minimum Number of Operations easy or hard?
The problem is classified as Medium because the brute idea is simple but the optimal solution requires recognizing the bounded value range and applying a greedy counting strategy to achieve O(n) time.
Equal Sum Arrays With Minimum Number of Operations Python/Java solution
Most implementations follow the greedy counting approach. Compute the sum difference, count potential improvements from each element, and greedily consume the largest reductions until the difference is eliminated. The same logic translates cleanly to Python, Java, C++, C#, and JavaScript.
How to solve Equal Sum Arrays With Minimum Number of Operations in O(n)?
First compute the sums of both arrays and determine the difference. For each element, calculate the maximum change it could contribute toward reducing that difference. Store counts of possible improvements (1 through 5). Greedily apply the largest improvements until the difference becomes zero or negative, which takes linear time.
What is the best approach for Equal Sum Arrays With Minimum Number of Operations?
The best approach is greedy difference reduction using counting. Calculate the sum difference between the arrays and track how much each element could change that difference (up to 5 because values range from 1 to 6). Process the largest possible reductions first using a frequency array. This runs in O(n) time and O(1) space.
Is Equal Sum Arrays With Minimum Number of Operations asked at Google/Amazon/Meta?
Greedy array optimization problems with bounded values appear frequently in interviews at companies like Amazon, Google, and Meta. This problem tests your ability to model operations as maximum improvements and apply greedy selection efficiently.
What data structure is used in Equal Sum Arrays With Minimum Number of Operations?
The optimal solution uses a counting array to track possible difference reductions. An alternative implementation uses a max heap (priority queue) to repeatedly select the operation with the largest impact.
What is the time complexity of Equal Sum Arrays With Minimum Number of Operations?
The optimal greedy counting solution runs in O(n) time where n is the total number of elements across both arrays. It uses O(1) extra space because the possible improvement values are limited to 1–5. A heap-based alternative runs in O(n log n) time due to priority queue operations.