2449. Minimum Number of Operations to Make Arrays Similar

HardGreedyArraySorting
Leetcode Link

Problem Description

You are given two arrays nums and target, each containing positive integers, and importantly, both are of the same length. Your task is to perform a specific operation as many times as needed to make the nums array similar to the target array. The operation allows you to choose two distinct indices i and j (both greater than or equal to 0 and less than the length of nums) and modify nums by increasing the value at nums[i] by 2 and decreasing the value at nums[j] by 2. An array is considered similar to another if both arrays contain the same elements with the same frequency, irrespective of their order.

You need to determine the minimum number of such operations needed to make nums similar to target.

Intuition

The key to solving this problem lies in recognizing that the order of elements in the arrays doesn't matter when comparing for similarity—only the frequency of each element matters. Therefore, both nums and target arrays can be sorted to ensure that elements with the same value are positioned at the same index. Sorting in such a way that the odd and even numbers are grouped together can simplify the comparison and the operations needed to convert nums into target.

After sorting both arrays, we go through each element of nums and target in a pairwise manner. For each pair (a, b) taken from nums and target respectively at the same index, we find the absolute difference between the two. This difference represents the total amount we would need to add or subtract to make nums[i] equal to target[i]. However, since our operations change values by 2 (adding 2 to one element and simultaneously subtracting 2 from another), the total number of operations will be the sum of all these differences divided by 4.

By taking this approach, we ensure that we are counting two operations (one addition and one subtraction) for every 4 integer difference between corresponding elements of nums and target.

Note that we can guarantee that nums can always be made similar to target as per the constraints given by the problem description.

Learn more about Greedy and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The implementation of the solution revolves around a simple but clever approach to transforming the nums array into the target array with the smallest number of operations as prescribed. The main algorithms and patterns used are sorting and pairwise element comparison. Here, we will walk through the steps taken in the provided solution code:

  • First, we sort both nums and target arrays with a custom sorting key. The lambda function provided as the key, lambda x: (x & 1, x), sorts the numbers first by whether they are odd or even (as determined by x & 1). By doing this, we group all the even numbers together and all the odd numbers together within each array. This arrangement is helpful because the operation we perform—adding or subtracting 2—cannot change an odd number into an even number, and vice versa.

  • The sort() method rearranges the nums and target arrays in-place, ensuring that elements of the same value within each array will align, which simplifies the comparison.

  • The next step involves a pairwise comparison of the sorted arrays. We iterate through the arrays using zip(nums, target), which creates pairs of elements (a, b) from corresponding indices in nums and target.

  • For each pair, we compute the absolute difference abs(a - b). The absolute difference tells us how far away the elements are from being equal, irrespective of which one is larger.

  • We accumulate this difference for each pair across the entire array. Once we have the total absolute difference, we need to understand how many operations are required to reconcile this difference. Since each operation changes the overall sum of two elements by 4 (increasing one element by 2 and decreasing another by 2), we divide the total absolute difference by 4. This division by 4 gives us the minimum number of operations required because we are effectively measuring how many 'blocks' of 4 the total difference adds up to.

The final return statement return sum(abs(a - b) for a, b in zip(nums, target)) // 4 neatly encapsulates the accumulation of differences and the calculation of the number of operations.

In terms of data structures, this solution uses the basic Python list and relies on built-in functions like sort() and abs() for sorting and computation. The use of the zip() function is another efficient way to handle pairing elements from the two lists in a simple loop.

This algorithm is very efficient because it avoids any unnecessary operations; no time is wasted trying to modify individual elements in a sequential or single-operation manner. The sort and comparison take O(n log n) and O(n) time respectively, resulting in a solution that is also very scalable with the array size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach described in the problem's content.

Suppose we have the following input:

  • nums array: [4, 1, 3, 7]
  • target array: [5, 2, 3, 8]

Both arrays are of length 4, which means we have four pairs of numbers to consider.

According to our solution approach, the first step is to sort both arrays while ensuring that odd and even numbers are grouped together. We use the custom lambda function lambda x: (x & 1, x) as our sorting key, where x & 1 groups odd numbers (result 1) and even numbers (result 0) together. After sorting:

  • Sorted nums array: [4, 3, 1, 7] (even numbers first, then odd numbers)
  • Sorted target array: [8, 3, 2, 5] (even numbers first, then odd numbers)

Next, we compare the sorted nums and target arrays pairwise and compute the absolute differences between corresponding elements:

  • Absolute differences: [|4-8|, |3-3|, |1-2|, |7-5|]
  • Calculated as: [4, 0, 1, 2]

Now we sum up these absolute differences to get the total amount of difference we need to reconcile:

  • Total absolute difference: 4 + 0 + 1 + 2 = 7

However, since each of our operations changes values by adding 2 to one element and subtracting 2 from another, we need to find out how many sets of 4 are in the total absolute difference. We divide the total absolute difference by 4 (the amount changed by a single operation) to find the minimum number of operations needed:

  • Number of operations: 7 // 4 = 1

Because dividing 7 by 4 gives us a remainder, we must round down to get the whole number of operations that are possible. Thus, the minimum number of operations required is 1.

It's important to note that because our operation moves two points at a time (one up and one down), when the total absolute difference is not a multiple of 4, this implies there may be leftover differences that cannot be fixed with the given operation. In our example, after performing the 1 operation we can on pair (4, 8), converting it to (6, 6), we'll be left with differences that can't be reconciled using the defined operation because the remaining differences are not multiples of 4.

Therefore, in this presented scenario, the solution errors in indicating that we could completely transform nums into target since odd and even numbers cannot be interchanged, and the remaining difference of 3 cannot be fixed in integer number operations.

However, within the context of the problem constraints where such a transformation is always possible, the above approach would yield the minimum number of operations required to make nums similar to target.

Solution Implementation

1class Solution:
2    def makeSimilar(self, nums: List[int], target: List[int]) -> int:
3        # Sort both nums and target lists first by odd-even status and then by value.
4        nums.sort(key=lambda x: (x % 2, x))  # Using % instead of & for clarity.
5        target.sort(key=lambda x: (x % 2, x))  # Using % instead of & for clarity.
6
7        # Calculate the sum of absolute differences between corresponding elements,
8        # divide by 4 to get the minimum number of operations required
9        # This works because an operation changes four numbers at a time.
10        operations = sum(abs(a - b) for a, b in zip(nums, target)) // 4
11
12        return operations
13
1class Solution {
2    public long makeSimilar(int[] nums, int[] target) {
3        // Sort both the input arrays to make positional comparison possible
4        Arrays.sort(nums);
5        Arrays.sort(target);
6
7        // Lists to store even and odd numbers from nums array
8        List<Integer> numsEvens = new ArrayList<>();
9        List<Integer> numsOdds = new ArrayList<>();
10
11        // Lists to store even and odd numbers from target array
12        List<Integer> targetEvens = new ArrayList<>();
13        List<Integer> targetOdds = new ArrayList<>();
14
15        // Distribute the numbers in nums into separate lists for evens and odds
16        for (int value : nums) {
17            if (value % 2 == 0) {
18                numsEvens.add(value);
19            } else {
20                numsOdds.add(value);
21            }
22        }
23
24        // Distribute the numbers in target into separate lists for evens and odds
25        for (int value : target) {
26            if (value % 2 == 0) {
27                targetEvens.add(value);
28            } else {
29                targetOdds.add(value);
30            }
31        }
32
33        // Initialize a variable to accumulate the differences
34        long totalDifference = 0;
35
36        // Calculate the difference between corresponding even numbers
37        for (int i = 0; i < numsEvens.size(); ++i) {
38            totalDifference += Math.abs(numsEvens.get(i) - targetEvens.get(i));
39        }
40
41        // Calculate the difference between corresponding odd numbers
42        for (int i = 0; i < numsOdds.size(); ++i) {
43            totalDifference += Math.abs(numsOdds.get(i) - targetOdds.get(i));
44        }
45
46        // Divide the total difference by 4, as per algorithm requirement, to get the answer.
47        return totalDifference / 4;
48    }
49}
50
1class Solution {
2public:
3    long long makeSimilar(vector<int>& nums, vector<int>& target) {
4        // Sort both the 'nums' and 'target' vectors.
5        sort(nums.begin(), nums.end());
6        sort(target.begin(), target.end());
7
8        // Separate the odd and even numbers from 'nums' into 'oddsNums' and 'evensNums'.
9        vector<int> oddsNums;
10        vector<int> evensNums;
11
12        // Separate the odd and even numbers from 'target' into 'oddsTarget' and 'evensTarget'.
13        vector<int> oddsTarget;
14        vector<int> evensTarget;
15
16        // Distribute the odd and even numbers from 'nums' into respective vectors.
17        for (int value : nums) {
18            if (value & 1) { // if the number is odd
19                oddsNums.emplace_back(value);
20            } else {
21                evensNums.emplace_back(value);
22            }
23        }
24
25        // Distribute the odd and even numbers from 'target' into respective vectors.
26        for (int value : target) {
27            if (value & 1) { // if the number is odd
28                oddsTarget.emplace_back(value);
29            } else {
30                evensTarget.emplace_back(value);
31            }
32        }
33
34        long long totalCost = 0; // Initialize the total cost to 0.
35
36        // Calculate the cost for making the odd parts of 'nums' and 'target' similar.
37        for (size_t i = 0; i < oddsNums.size(); ++i) {
38            totalCost += abs(oddsNums[i] - oddsTarget[i]);
39        }
40      
41        // Calculate the cost for making the even parts of 'nums' and 'target' similar.
42        for (size_t i = 0; i < evensNums.size(); ++i) {
43            totalCost += abs(evensNums[i] - evensTarget[i]);
44        }
45
46        // Since each swap consists of 2 increments or decrements, divide the total cost by 4.
47        return totalCost / 4;
48    }
49};
50
1function makeSimilar(nums: number[], target: number[]): number {
2    // Sort both arrays in non-decreasing order
3    nums.sort((a, b) => a - b);
4    target.sort((a, b) => a - b);
5
6    // Initialize empty arrays to hold even and odd elements separately
7    const evensFromNums: number[] = [];
8    const oddsFromNums: number[] = [];
9    const evensFromTarget: number[] = [];
10    const oddsFromTarget: number[] = [];
11
12    // Separate even and odd numbers from the original nums array
13    for (const value of nums) {
14        if (value % 2 === 0) {
15            evensFromNums.push(value);
16        } else {
17            oddsFromNums.push(value);
18        }
19    }
20
21    // Separate even and odd numbers from the target array
22    for (const value of target) {
23        if (value % 2 === 0) {
24            evensFromTarget.push(value);
25        } else {
26            oddsFromTarget.push(value);
27        }
28    }
29
30    // Initialize the accumulator for the total difference
31    let totalDifference = 0;
32
33    // Calculate the total difference between the even elements from nums and target
34    for (let i = 0; i < evensFromNums.length; ++i) {
35        totalDifference += Math.abs(evensFromNums[i] - evensFromTarget[i]);
36    }
37
38    // Calculate the total difference between the odd elements from nums and target
39    for (let i = 0; i < oddsFromNums.length; ++i) {
40        totalDifference += Math.abs(oddsFromNums[i] - oddsFromTarget[i]);
41    }
42
43    // Return the result as the total difference divided by 4
44    return totalDifference / 4;
45}
46
Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down into the major operations it performs:

  1. nums.sort(key=lambda x: (x & 1, x)): Sorting the nums list. The sorting operation typically has a time complexity of O(n log n), where n is the number of elements in nums.

  2. target.sort(key=lambda x: (x & 1, x)): Similarly, sorting the target list also has a time complexity of O(n log n).

  3. sum(abs(a - b) for a, b in zip(nums, target)): Zipping the two lists and calculating the sum of absolute differences has a linear time complexity, O(n), since it processes each pair of elements once.

When combining these operations, the dominant factor is the sorting steps, so the overall time complexity of the makeSimilar function is O(n log n).

Space Complexity

The space complexity of the given code can be analyzed as follows:

  1. Sorting both the nums and target lists is done in-place in Python (Timsort), which has a space complexity of O(n) in the worst case, as it may require temporary space to hold elements while sorting.

  2. The generator expression within the sum function has a space complexity of O(1), as it computes the absolute differences on-the-fly without storing them.

  3. No additional significant space is used in the function.

Therefore, the overall space complexity of the makeSimilar function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫