Minimum Number of Operations to Make Arrays Similar Solution
Minimum Number of Operations to Make Arrays Similar solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Number of Operations to Make Arrays Similar is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Walmart interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Walmart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two positive integer arrays nums and target of the same length. In one operation you choose two different indices i and j and set nums[i] = nums[i] + 2 and nums[j] = nums[j] - 2.
Two arrays are similar when every value occurs the same number of times in both (they are equal after sorting).
Return the minimum number of operations that makes nums similar to target. The input guarantees this is possible.
The original allows values up to 10^6; here values are at most 10^4 so the answer fits in a 32-bit integer.
Example 1
Input: nums = [5,10,3], target = [9,6,3]
Output: 2
Explanation: Twice: add 2 to the 5 and subtract 2 from the 10, reaching `[9,6,3]`.
Example 2
Input: nums = [8,12,6], target = [2,14,10]
Output: 2
Example 3
Input: nums = [1,1,1,1,1], target = [1,1,1,1,1]
Output: 0
Constraints
n == nums.length == target.length1 <= n <= 10^51 <= nums[i], target[i] <= 10^4nums can always be made similar to target
Hints for Minimum Number of Operations to Make Arrays Similar
Hint 1
An operation changes values by 2, so an odd value always stays odd and an even value stays even.
Hint 2
Odd values must be matched with odd targets, even with even. Within each parity, which matching is cheapest?
Hint 3
Sort each parity group of both arrays and pair them in order. The total
sum |nums - target|over the pairs is moved 4 units per operation.
How to solve Minimum Number of Operations to Make Arrays Similar
Parity never changes, so odd values are matched to odd targets and even to even. Within each class, matching sorted to sorted minimises the total distance, and each operation closes exactly 4 units of distance (+2 on one element, −2 on another).
Approach
- Split
numsandtargetinto odd and even values and sort each of the four lists. - Pair the i-th smallest odd value of
numswith the i-th smallest odd target, and the same for even values. - Sum
|a - b|over all pairs (in 64-bit) and return the sum divided by 4.
Why it works
Fix a matching. Every element must move by an even amount; one operation raises one element by 2 and lowers another by 2, so the number of operations is at least half the total increase, i.e. a quarter of the total absolute distance — and that is achievable by pairing raises with lowers. Matching sorted lists in order minimises the total absolute distance (crossing pairs can always be uncrossed without increasing it).
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Sorting the whole arrays together mixes parities and gives wrong pairs.
- Divide by 4, not 2: each operation reduces the total distance by 4.
- Accumulate the distance in 64 bits under the original bounds.
Reference solution
Python
from typing import List
def makeSimilar(nums: List[int], target: List[int]) -> int:
total = 0
for r in (0, 1):
a = sorted(x for x in nums if x % 2 == r)
b = sorted(x for x in target if x % 2 == r)
total += sum(abs(x - y) for x, y in zip(a, b))
return total // 4Java
public static int makeSimilar(int[] nums, int[] target) {
int[] a = nums.clone(), b = target.clone();
Arrays.sort(a);
Arrays.sort(b);
long total = 0;
for (int r = 0; r < 2; r++) {
int i = 0, j = 0;
while (true) {
while (i < a.length && a[i] % 2 != r) i++;
while (j < b.length && b[j] % 2 != r) j++;
if (i >= a.length || j >= b.length) break;
total += Math.abs(a[i] - b[j]);
i++;
j++;
}
}
return (int) (total / 4);
}C++
int makeSimilar(vector<int>& nums, vector<int>& target) {
long long total = 0;
for (int r = 0; r < 2; r++) {
vector<int> a, b;
for (int x : nums) if (x % 2 == r) a.push_back(x);
for (int x : target) if (x % 2 == r) b.push_back(x);
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for (size_t i = 0; i < a.size(); i++) total += abs(a[i] - b[i]);
}
return (int)(total / 4);
}JavaScript
var makeSimilar = function(nums, target) {
var part = function(arr, r) {
return arr.filter(function(x) { return x % 2 === r; }).sort(function(x, y) { return x - y; });
};
var total = 0;
for (var r = 0; r < 2; r++) {
var a = part(nums, r), b = part(target, r);
for (var i = 0; i < a.length; i++) total += Math.abs(a[i] - b[i]);
}
return total / 4;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms