Minimum Number of Operations to Make Arrays Similar

Hard Arrays & Hashing Greedy Original on LeetCode

Minimum Number of Operations to Make Arrays Similar is a hard arrays & hashing problem solved with the greedy pattern. The best approach, optimal (split by parity, sort, pair up), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (match by repeated scanning) up.

Problem

You are given two positive integer arrays nums and target of the same length. In one operation you pick two different indices i and j and do nums[i] += 2 and nums[j] -= 2 at the same time.

The two arrays are similar when each value occurs the same number of times in both (order does not matter). Return the minimum number of operations needed to make nums similar to target. The input always allows this.

Examples

Example 1

Input
nums = [9, 4, 2], target = [5, 6, 4]
Output
2
Why
Lower 9 by 2 while raising 2 to 4, then lower 7 to 5 while raising 4 to 6. nums becomes [5, 6, 4], which has the same values as target.

Example 2

Input
nums = [1, 3, 5], target = [5, 1, 3]
Output
0
Why
Both arrays already contain the same values, only in a different order.

Example 3

Input
nums = [10, 1, 2, 7], target = [4, 3, 6, 7]
Output
2
Why
Odd values pair as 1→3 and 7→7, even values as 2→4 and 10→6. The total surplus is 4, and every operation removes 2 of it.

Constraints

  • n == nums.length == target.length, 1 <= n <= 10^5
  • 1 <= nums[i], target[i] <= 10^6
  • It is guaranteed that nums can always be made similar to target.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (match by repeated scanning)O(n²)O(n)
Optimal (split by parity, sort, pair up)O(n log n)O(n)

1Brute force (match by repeated scanning)

TimeO(n²)Each of the n values scans all n targets.
SpaceO(n)The used flags.

Within each parity class, matching the smallest value with the smallest target, the next with the next, and so on, is optimal. Build that matching without sorting the targets: take the values in ascending order and, for each, scan for the smallest unused target of the same parity. Add up the positive differences; every operation removes exactly 2 of that surplus.

  1. Sort nums. Mark every target as unused.
  2. For each value v in nums, scan target for the smallest unused t with the same parity as v; mark it used.
  3. If v > t, add v - t to surplus.
  4. Return surplus / 2.
class Solution {
    public long makeSimilar(int[] nums, int[] target) {
        int n = nums.length;
        int[] a = nums.clone();
        Arrays.sort(a);
        boolean[] used = new boolean[n];
        long surplus = 0;
        for (int v : a) {
            int best = -1;
            for (int j = 0; j < n; j++)
                if (!used[j] && target[j] % 2 == v % 2 && (best == -1 || target[j] < target[best])) best = j;
            used[best] = true;
            if (v > target[best]) surplus += v - target[best];
        }
        return surplus / 2;
    }
}

2Optimal (split by parity, sort, pair up)

TimeO(n log n)Two sorts plus one linear pass.
SpaceO(n)Sorted copies of the arrays.

Separate both arrays into odd and even values and sort each of the four lists. Pair the i-th odd value with the i-th odd target and the i-th even value with the i-th even target (sorted pairing never crosses, so it minimises the total movement). Each operation moves 2 units from one surplus to one deficit, so the answer is the total surplus divided by 2.

  1. Sort nums and target with odd values first, then even values, each part ascending (a comparator on (parity, value) does this).
  2. For each index i, if nums[i] > target[i], add the difference.
  3. Return the sum / 2.
class Solution {
    public long makeSimilar(int[] nums, int[] target) {
        int[] a = order(nums), b = order(target);
        long surplus = 0;
        for (int i = 0; i < a.length; i++)
            if (a[i] > b[i]) surplus += a[i] - b[i];
        return surplus / 2;
    }

    private int[] order(int[] x) {
        int[] r = x.clone();
        // odd values become negative, so they sort first, then evens; both parts ascending
        for (int i = 0; i < r.length; i++) if (r[i] % 2 == 1) r[i] = r[i] - 2_000_000;
        Arrays.sort(r);
        for (int i = 0; i < r.length; i++) if (r[i] < 0) r[i] += 2_000_000;
        return r;
    }
}

Edge cases to test

  • Already similar (possibly in a different order): 0
  • A single element: it must already match, so 0
  • Only odd or only even values
  • Large values and large n, where the answer needs 64 bits

Hints

Hint 1

Adding or subtracting 2 never changes a number's parity, so odd values can only turn into odd target values, and even into even.

Hint 2

Within one parity class, which value should become which target value? Exchanging two assignments never helps if you match them in sorted order.

Hint 3

Each operation lowers the total positive gap by exactly 2, so the answer is (sum of positive differences) / 2.

FAQ

What is the best time complexity for Minimum Number of Operations to Make Arrays Similar?

Optimal (split by parity, sort, pair up) runs in O(n log n) time and O(n) extra space. Two sorts plus one linear pass.

Which pattern does Minimum Number of Operations to Make Arrays Similar use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Minimum Number of Operations to Make Arrays Similar?

Yes. Brute force (match by repeated scanning) takes O(n²) time and O(n) space. Within each parity class, matching the smallest value with the smallest target, the next with the next, and so on, is optimal.

Which edge cases should I test for Minimum Number of Operations to Make Arrays Similar?

Already similar (possibly in a different order): 0; A single element: it must already match, so 0; Only odd or only even values; Large values and large n, where the answer needs 64 bits.