Minimum Number of Operations to Make Arrays Similar

Hard
1467.

Minimum Number of Operations to Make Arrays Similar

Minimum Number of Operations to Make Arrays Similar is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Walmart interviews.

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.length
  • 1 <= n <= 10^5
  • 1 <= nums[i], target[i] <= 10^4
  • nums can always be made similar to target
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} target
 * @return {number}
 */
var makeSimilar = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 10^5
  • 1 <= nums[i], target[i] <= 10^4
  • nums can always be made similar to target

Hints for Minimum Number of Operations to Make Arrays Similar

  1. Hint 1

    An operation changes values by 2, so an odd value always stays odd and an even value stays even.

  2. Hint 2

    Odd values must be matched with odd targets, even with even. Within each parity, which matching is cheapest?

  3. 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

  1. Split nums and target into odd and even values and sort each of the four lists.
  2. Pair the i-th smallest odd value of nums with the i-th smallest odd target, and the same for even values.
  3. 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 // 4

Java

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