Minimum Number of Operations to Make Arrays Similar

Hard

#2233Time: O(k! * k + (n-k)! * (n-k)), where `k` is the number of odd elements. This is prohibitively slow.Space: O(n), to store the separated lists for odd and even numbers and the permutations.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

You are given two positive integer arrays nums and target, of the same length.

In one operation, you can choose any two distinct indices i and j where 0 <= i, j < nums.length and:

set nums[i] = nums[i] + 2 and
set nums[j] = nums[j] - 2.

Two arrays are considered to be similar if the frequency of each element is the same.

Return the minimum number of operations required to make nums similar to target. The test cases are generated such that nums can always be similar to target.

Example 1:

Input: nums = [8,12,6], target = [2,14,10]
Output: 2
Explanation: It is possible to make nums similar to target in two operations:
- Choose i = 0 and j = 2, nums = [10,12,4].
- Choose i = 1 and j = 2, nums = [10,14,2].
It can be shown that 2 is the minimum number of operations needed.

Example 2:

Input: nums = [1,2,5], target = [4,1,3]
Output: 1
Explanation: We can make nums similar to target in one operation:
- Choose i = 1 and j = 2, nums = [1,4,3].

Example 3:

Input: nums = [1,1,1,1,1], target = [1,1,1,1,1]
Output: 0
Explanation: The array nums is already similiar to target.

Constraints:

n == nums.length == target.length
1 <= n <= 10⁵
1 <= nums[i], target[i] <= 10⁶
It is possible to make nums similar to target.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem by exploring every possible way to pair the numbers from nums with the numbers from target. Since numbers can only be transformed into other numbers of the same parity, we only need to consider pairings within the odd and even groups. The method calculates the transformation cost for every single permutation of pairings and finds the minimum among them.

Algorithm

Separate the nums and target arrays into four lists based on parity: nums_odd, nums_even, target_odd, and target_even.
Initialize a variable min_operations to a very large value.
Generate all possible permutations of the target_odd list.
For each permutation of target_odd:
- Generate all possible permutations of the target_even list.
- For each permutation of target_even:
  - Calculate the total positive difference required to transform nums into this pairing. This is done by summing up max(0, p_odd[i] - nums_odd[i]) for all i in the odd lists and max(0, p_even[i] - nums_even[i]) for all i in the even lists.
  - The number of operations for this specific pairing is the total positive difference divided by 2.
  - Update min_operations with the minimum value found so far.
Return min_operations.

Walkthrough

The fundamental observation is that an operation nums[i] += 2, nums[j] -= 2 preserves the parity of both nums[i] and nums[j]. This means we can consider the problem of transforming the odd numbers in nums to the odd numbers in target separately from the even numbers.

This brute-force approach enumerates all possible one-to-one mappings (permutations) from the odd numbers in nums to the odd numbers in target, and similarly for the even numbers. For each complete mapping, it calculates the total number of operations required. The total increase needed is the sum of all positive differences (target_val - nums_val). Since each operation provides a +2 increase, the number of operations is this sum divided by 2. The algorithm finds the minimum cost over all possible permutations.

However, the number of permutations is k! (k-factorial), where k is the number of elements in the list. Given that n can be up to 10^5, this approach is computationally impossible in practice.

Complexity

Time

O(k! * k + (n-k)! * (n-k)), where `k` is the number of odd elements. This is prohibitively slow.

Space

O(n), to store the separated lists for odd and even numbers and the permutations.

Trade-offs

Pros

Demonstrates a basic understanding of the problem's combinatorial nature.

Cons

Extremely high time complexity, making it infeasible for all but the smallest input sizes.
Complex to implement correctly due to the need for permutation generation.

A much more efficient approach is based on a greedy strategy. After separating the numbers by parity, we sort both the nums and target sub-lists. The key insight is that to minimize the total number of operations, we should pair the smallest numbers with the smallest, the second smallest with the second smallest, and so on. This is because this pairing minimizes the sum of absolute differences, which in turn minimizes the total increase required. The total number of operations is then half of the total increase needed across all numbers.

Algorithm

Create four lists: nums_odd, nums_even, target_odd, and target_even.
Iterate through the input arrays nums and target. Populate the four lists by checking the parity of each number.
Sort all four lists in ascending order.
Initialize a long variable positive_diff_sum to 0.
Iterate through the sorted odd lists from i = 0 to nums_odd.size() - 1. Calculate the difference d = target_odd.get(i) - nums_odd.get(i). If d is positive, add it to positive_diff_sum.
Iterate through the sorted even lists from i = 0 to nums_even.size() - 1. Calculate the difference d = target_even.get(i) - nums_even.get(i). If d is positive, add it to positive_diff_sum.
The total minimum number of operations is positive_diff_sum / 2. Return this value.

Walkthrough

This approach leverages two key insights. First, since operations preserve parity, we can handle odd and even numbers as two independent subproblems. Second, the minimum number of operations is achieved by a greedy pairing strategy. To minimize the sum of transformations, it's always optimal to transform the i-th smallest number in nums (of a certain parity) to the i-th smallest number in target (of the same parity). This is a known property related to the rearrangement inequality.

The algorithm proceeds as follows:

Segregate nums and target into lists of odd and even numbers.
Sort these four lists. This allows us to easily pair the i-th smallest elements.
Calculate the total increase required. We iterate through the sorted lists and sum up all the positive differences (target[i] - nums[i] > 0). Let this be positive_diff_sum.
The total decrease required will be equal to the total increase required because the sum of elements in nums and target are equal. Each operation consists of one +2 and one -2. Therefore, the total number of operations is simply the total increase needed divided by 2.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public long minOperations(int[] nums, int[] target) {7        List<Integer> numsOdd = new ArrayList<>();8        List<Integer> numsEven = new ArrayList<>();9        List<Integer> targetOdd = new ArrayList<>();10        List<Integer> targetEven = new ArrayList<>();11 12        for (int num : nums) {13            if (num % 2 == 0) {14                numsEven.add(num);15            } else {16                numsOdd.add(num);17            }18        }19 20        for (int num : target) {21            if (num % 2 == 0) {22                targetEven.add(num);23            } else {24                targetOdd.add(num);25            }26        }27 28        Collections.sort(numsOdd);29        Collections.sort(numsEven);30        Collections.sort(targetOdd);31        Collections.sort(targetEven);32 33        long positiveDiffSum = 0;34 35        for (int i = 0; i < numsOdd.size(); i++) {36            int diff = targetOdd.get(i) - numsOdd.get(i);37            if (diff > 0) {38                // The difference must be even. We add half of it to the count of operations.39                positiveDiffSum += diff;40            }41        }42 43        for (int i = 0; i < numsEven.size(); i++) {44            int diff = targetEven.get(i) - numsEven.get(i);45            if (diff > 0) {46                positiveDiffSum += diff;47            }48        }49 50        // Each operation increases one number by 2. The total increase needed is positiveDiffSum.51        // So, the number of operations is positiveDiffSum / 2.52        return positiveDiffSum / 2;53    }54}

Complexity

Time

O(n log n), dominated by the sorting of the odd and even sub-lists. Separating the numbers takes O(n) and calculating the final sum takes O(n).

Space

O(n), for storing the four lists of odd and even numbers. In the worst case, one pair of lists can contain up to n elements.

Trade-offs

Pros

Highly efficient with a time complexity of O(n log n).
Guaranteed to find the minimum number of operations.
The logic is straightforward and relatively easy to implement.

Cons

Requires O(n) extra space to hold the separated lists.

Solutions

Solution

1class Solution {2public3  long makeSimilar(int[] nums, int[] target) {4    Arrays.sort(nums);5    Arrays.sort(target);6    List<Integer> a1 = new ArrayList<>();7    List<Integer> a2 = new ArrayList<>();8    List<Integer> b1 = new ArrayList<>();9    List<Integer> b2 = new ArrayList<>();10    for (int v : nums) {11      if (v % 2 == 0) {12        a1.add(v);13      } else {14        a2.add(v);15      }16    }17    for (int v : target) {18      if (v % 2 == 0) {19        b1.add(v);20      } else {21        b2.add(v);22      }23    }24    long ans = 0;25    for (int i = 0; i < a1.size(); ++i) {26      ans += Math.abs(a1.get(i) - b1.get(i));27    }28    for (int i = 0; i < a2.size(); ++i) {29      ans += Math.abs(a2.get(i) - b2.get(i));30    }31    return ans / 4;32  }33}

1class Solution:2    def makeSimilar(self, nums: List[int], target: List[int]) -> int: nums . sort(key=lambda x: (x & 1, x)) target . sort(key=lambda x: (x & 1, x)) return sum(abs(a - b) for a, b in zip(nums, target)) // 4

1class Solution { public: long long makeSimilar ( vector < int >& nums , vector < int >& target ) { sort ( nums . begin (), nums . end ()); sort ( target . begin (), target . end ()); vector < int > a1 ; vector < int > a2 ; vector < int > b1 ; vector < int > b2 ; for ( int v : nums ) { if ( v & 1 ) a1 . emplace_back ( v ); else a2 . emplace_back ( v ); } for ( int v : target ) { if ( v & 1 ) b1 . emplace_back ( v ); else b2 . emplace_back ( v ); } long long ans = 0 ; for ( int i = 0 ; i < a1 . size (); ++ i ) ans += abs ( a1 [ i ] - b1 [ i ]); for ( int i = 0 ; i < a2 . size (); ++ i ) ans += abs ( a2 [ i ] - b2 [ i ]); return ans / 4 ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem