Minimum Number of Operations to Make Arrays Similar solution and explanation
9 more videos on this problem
Leetcode 2449 Minimum Number of Operations to Make Arrays SimilarThinkCode · 8:21 · 1K views
Weekly Contest 316 | 2449. Minimum Number of Operations to Make Arrays SimilarcodingMohan · 19:37 · 982 views
Leetcode Weekly contest 316 - Hard - Minimum Number of Operations to Make Arrays SimilarPrakhar Agrawal · 12:29 · 832 views
2449. Minimum Number of Operations to Make Arrays Similar (Leetcode Hard)Programming Live with Larry · 17:14 · 493 views
【每日一题】LeetCode 2449. Minimum Number of Operations to Make Arrays SimilarHuifeng Guan · 21:17 · 450 views
Leetcode 2449. Minimum Number of Operations to Make Arrays SimilarAlgorithms Casts · 14:26 · 211 views
2449 Minimum Number of Operations to Make Arrays Similar | Leetcode Weekly contest 316Ashutosh sharma · 11:42 · 189 views
leetcode 2449. Minimum Number of Operations to Make Arrays Similar - observe invariant quantitiesCode-Yao · 11:54 · 100 views
Weekly Contest 316 | 2449. Minimum Number of Operations to Make Arrays SimilarCodeHub · 11:17 · 61 views
Leetcode Weekly Contest 316 2449 Minimum Number of Operations to Make Arrays SimilarEric Websmith · 5:50 · 26 views
The problem
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] + 2and - 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.length1 <= n <= 1051 <= nums[i], target[i] <= 106- It is possible to make
numssimilar totarget.
Approach overview
Problem Overview: You are given two integer arrays nums and target. In one operation, you can choose two indices in nums, add 2 to one element and subtract 2 from the other. The goal is to transform nums so it becomes similar to target, meaning both arrays contain the same multiset of values. The task is to compute the minimum number of operations required.
Approach 1: Greedy Approach with Sorting (O(n log n) time, O(n) space)
The key observation: adding or subtracting 2 never changes the parity of a number. Odd numbers must match with odd numbers, and even numbers must match with even numbers. Split both arrays into two groups based on parity. Sort the odd elements of nums and target, and do the same for the even elements. Then compare corresponding elements and accumulate the positive differences. Each operation effectively shifts 2 units between elements, so the total difference divided appropriately gives the operation count. Sorting ensures the smallest values match first, which minimizes total adjustment. This approach uses classic greedy matching combined with sorting to minimize unnecessary adjustments.
Approach 2: Frequency Matching by Counting and Remainder Groups (O(n log n) or O(n) time depending on map usage, O(n) space)
Another perspective is to track how much adjustment each element requires relative to its matching parity group. Separate elements into odd and even buckets, then sort or frequency-count them. Compute the difference between each pair of corresponding elements. Only positive differences matter because decreases are balanced by increases elsewhere due to the operation structure. Each increase of 2 contributes toward the total operation count. Instead of directly simulating operations, aggregate the total increments needed and divide by 2. Using counting or frequency maps reduces repeated scanning when many values repeat. This approach still relies on the parity constraint but focuses on difference aggregation rather than pairwise greedy matching.
Recommended for interviews: The greedy sorting approach is the expected solution. It clearly shows you recognize the invariant that parity never changes and that matching sorted parity groups minimizes adjustment cost. Interviewers usually want to see the reasoning about parity first, then a clean greedy implementation using arrays or lists. Understanding the parity constraint comes from analyzing the allowed operation on the array, which is the core trick behind this hard problem.
Approach 1: Greedy Approach with Sorting
This approach involves sorting both the 'nums' and 'target' arrays. The idea is to pair the elements of the two arrays in a sorted manner, and compute the difference needed to transform each element of 'nums' to become the element in 'target'. We accumulate the absolute difference divided by 2 (since each operation can adjust a pair by 2), hence calculating the minimum number of operations required.
def minOperations(nums, target):
nums.sort()
target.sort()
total_diff = 0
for n, t in zip(nums, target):
total_diff += abs(n - t)
return total_diff // 2
# Example usage:
# nums = [8,12,6]
# target = [2,14,10]
# Result: 2import java.util.Arrays;
public int minOperations(int[] nums, int[] target) {
Arrays.sort(nums);
Arrays.sort(target);
int totalDiff = 0;
for (int i = 0; i < nums.length; i++) {
totalDiff += Math.abs(nums[i] - target[i]);
}
return totalDiff / 2;
}
// Example usage:
// int[] nums = {8, 12, 6};
// int[] target = {2, 14, 10};
// Result: 2#include <algorithm>
#include <vector>
int minOperations(std::vector<int>& nums, std::vector<int>& target) {
std::sort(nums.begin(), nums.end());
std::sort(target.begin(), target.end());
int totalDiff = 0;
for (size_t i = 0; i < nums.size(); ++i) {
totalDiff += abs(nums[i] - target[i]);
}
return totalDiff / 2;
}
// Example usage:
// std::vector<int> nums = {8, 12, 6};
// std::vector<int> target = {2, 14, 10};
// Result: 2function minOperations(nums, target) {
nums.sort((a, b) => a - b);
target.sort((a, b) => a - b);
let totalDiff = 0;
for (let i = 0; i < nums.length; i++) {
totalDiff += Math.abs(nums[i] - target[i]);
}
return totalDiff / 2;
}
// Example usage:
// let nums = [8, 12, 6];
// let target = [2, 14, 10];
// Result: 2#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int minOperations(int* nums, int numsSize, int* target, int targetSize) {
qsort(nums, numsSize, sizeof(int), compare);
qsort(target, targetSize, sizeof(int), compare);
int totalDiff = 0;
for (int i = 0; i < numsSize; i++) {
totalDiff += abs(nums[i] - target[i]);
}
return totalDiff / 2;
}
// Example usage:
// int nums[] = {8, 12, 6};
// int target[] = {2, 14, 10};
// Result: 2using System;
public class Solution {
public int MinOperations(int[] nums, int[] target) {
Array.Sort(nums);
Array.Sort(target);
int totalDiff = 0;
for (int i = 0; i < nums.Length; i++) {
totalDiff += Math.Abs(nums[i] - target[i]);
}
return totalDiff / 2;
}
}
// Example usage:
// int[] nums = {8, 12, 6};
// int[] target = {2, 14, 10};
// Result: 2In Python, after sorting the arrays, we use the 'zip' function to traverse elements from both arrays simultaneously. For each pair, we compute the absolute difference and accumulate it. Finally, this total difference is divided by 2 since one operation changes two elements by 2 units, yielding the minimum number of operations required.
Time Complexity: O(n log n) due to the sorting operations.
Space Complexity: O(1), as no additional data structures are used.
Approach 2: Frequency Matching by Counting and Matching Remainders
In this approach, consider the problem from a remainder perspective. Since adding 2 or subtracting 2 does not change the evenness or oddness of the numbers, instead of transforming the entire number, only focus on ensuring the ratios of odd and even numbers are maintained. Count the number of odd and even entries in both arrays. Pair excess even numbers in 'nums' with missing evens in 'target', and do the same with odd numbers.
def minOperations(nums, target):
odd_diff = even_diff = 0
for n, t in zip(nums, target):
if n % 2 != t % 2:
if n % 2 == 0:
even_diff += 1
else:
odd_diff += 1
return max(odd_diff, even_diff)
# Example usage:
# nums = [8,12,6]
# target = [2,14,10]
# Result: 2public int minOperations(int[] nums, int[] target) {
int oddDiff = 0, evenDiff = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] % 2 != target[i] % 2) {
if (nums[i] % 2 == 0) evenDiff++;
else oddDiff++;
}
}
return Math.max(oddDiff, evenDiff);
}
// Example usage:
// int[] nums = {8, 12, 6};
// int[] target = {2, 14, 10};
// Result: 2#include <vector>
int minOperations(std::vector<int>& nums, std::vector<int>& target) {
int oddDiff = 0, evenDiff = 0;
for (size_t i = 0; i < nums.size(); ++i) {
if (nums[i] % 2 != target[i] % 2) {
if (nums[i] % 2 == 0) evenDiff++;
else oddDiff++;
}
}
return std::max(oddDiff, evenDiff);
}
// Example usage:
// std::vector<int> nums = {8, 12, 6};
// std::vector<int> target = {2, 14, 10};
// Result: 2function minOperations(nums, target) {
let oddDiff = 0, evenDiff = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] % 2 !== target[i] % 2) {
if (nums[i] % 2 === 0) evenDiff++;
else oddDiff++;
}
}
return Math.max(oddDiff, evenDiff);
}
// Example usage:
// let nums = [8, 12, 6];
// let target = [2, 14, 10];
// Result: 2int minOperations(int* nums, int numsSize, int* target, int targetSize) {
int oddDiff = 0, evenDiff = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] % 2 != target[i] % 2) {
if (nums[i] % 2 == 0) evenDiff++;
else oddDiff++;
}
}
return (oddDiff > evenDiff) ? oddDiff : evenDiff;
}
// Example usage:
// int nums[] = {8, 12, 6};
// int target[] = {2, 14, 10};
// Result: 2public int MinOperations(int[] nums, int[] target) {
int oddDiff = 0, evenDiff = 0;
for (int i = 0; i < nums.Length; i++) {
if (nums[i] % 2 != target[i] % 2) {
if (nums[i] % 2 == 0) evenDiff++;
else oddDiff++;
}
}
return Math.Max(oddDiff, evenDiff);
}
// Example usage:
// int[] nums = {8, 12, 6};
// int[] target = {2, 14, 10};
// Result: 2By processing both lists element-wise, if an even number in 'nums' needs to be odd in 'target' or vice-versa, increment respective counters. The maximum discrepancy between odd and even shifts gives the minimum operations required to match odd/even distribution.
Time Complexity: O(n), linear scan through arrays.
Space Complexity: O(1), counters for odd/even differences.
Approach 3: Odd-Even Classification + Sorting
Notice that, because each operation will only increase or decrease the value of an element by 2, the parity of the element will not change.
Therefore, we can divide the arrays nums and target into two groups according to their parity, denoted as a_1 and a_2, and b_1 and b_2 respectively.
Then, we just need to pair the elements in a_1 with the elements in b_1, and pair the elements in a_2 with the elements in b_2, and then perform operations. During the pairing process, we can use a greedy strategy, pairing the smaller elements in a_i with the smaller elements in b_i each time, which can ensure the minimum number of operations. This can be directly implemented through sorting.
Since each operation can reduce the difference of the corresponding elements by 4, we accumulate the difference of each corresponding position, and finally divide by 4 to get the answer.
The time complexity is O(n times log n), where n is the length of the array nums.
function makeSimilar(nums: number[], target: number[]): number {
nums.sort((a, b) => a - b);
target.sort((a, b) => a - b);
const a1: number[] = [];
const a2: number[] = [];
const b1: number[] = [];
const b2: number[] = [];
for (const v of nums) {
if (v % 2 === 0) {
a1.push(v);
} else {
a2.push(v);
}
}
for (const v of target) {
if (v % 2 === 0) {
b1.push(v);
} else {
b2.push(v);
}
}
let ans = 0;
for (let i = 0; i < a1.length; ++i) {
ans += Math.abs(a1[i] - b1[i]);
}
for (let i = 0; i < a2.length; ++i) {
ans += Math.abs(a2[i] - b2[i]);
}
return ans / 4;
}func makeSimilar(nums []int, target []int) int64 {
sort.Ints(nums)
sort.Ints(target)
a1, a2, b1, b2 := []int{}, []int{}, []int{}, []int{}
for _, v := range nums {
if v%2 == 0 {
a1 = append(a1, v)
} else {
a2 = append(a2, v)
}
}
for _, v := range target {
if v%2 == 0 {
b1 = append(b1, v)
} else {
b2 = append(b2, v)
}
}
ans := 0
for i := 0; i < len(a1); i++ {
ans += abs(a1[i] - b1[i])
}
for i := 0; i < len(a2); i++ {
ans += abs(a2[i] - b2[i])
}
return int64(ans / 4)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to the sorting operations. |
| Frequency Matching by Counting and Matching Remainders | Time Complexity: O(n), linear scan through arrays. |
| Odd-Even Classification + Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Matching with Sorting | O(n log n) | O(n) | General case. Clean and reliable solution used in most interviews. |
| Frequency Matching by Parity Groups | O(n log n) or O(n) | O(n) | Useful when many duplicate values exist or when implementing difference aggregation. |
Frequently asked questions
Is Minimum Number of Operations to Make Arrays Similar easy or hard?
The problem is rated Hard because the key constraint is not immediately obvious. Recognizing that operations preserve parity is the main insight. Once that observation is made, the solution reduces to greedy matching with sorting.
Minimum Number of Operations to Make Arrays Similar Python/Java solution
Most implementations follow the same pattern: split nums and target into odd and even lists, sort each list, then sum positive differences between corresponding elements. This logic translates directly to Python, Java, C++, and JavaScript with identical O(n log n) complexity.
How to solve Minimum Number of Operations to Make Arrays Similar in O(n)?
A near O(n) solution can be achieved using counting or frequency maps when value ranges are manageable. Elements are grouped by parity, then differences between required and current frequencies are aggregated. The total adjustment divided by 2 gives the operation count.
What is the best approach for Minimum Number of Operations to Make Arrays Similar?
The most effective approach is greedy matching with sorting. Separate both arrays into odd and even groups because operations of +/-2 never change parity. Sort each parity group and compare corresponding elements to compute the required adjustments. This approach runs in O(n log n) time and O(n) space.
Is Minimum Number of Operations to Make Arrays Similar asked at Google/Amazon/Meta?
Greedy and parity-based transformation problems similar to this appear in interviews at companies like Google, Amazon, and Meta. They test recognition of invariants, greedy matching, and efficient use of sorting or frequency counting.
What data structure is used in Minimum Number of Operations to Make Arrays Similar?
The solution primarily uses arrays or lists to separate odd and even numbers. Sorting algorithms and sometimes hash maps or frequency counters are used to match elements and compute required differences efficiently.
What is the time complexity of Minimum Number of Operations to Make Arrays Similar?
The optimal solution runs in O(n log n) time due to sorting the parity-separated arrays. After sorting, a single pass computes the difference between elements to determine the number of operations. Space complexity is O(n) for storing the separated groups.