You are given two integer arrays arr and brr of length n, and an integer k. You can perform the following operations on arr any number of times:
arr into any number of contiguous subarrays and rearrange these subarrays in any order. This operation has a fixed cost of k.Choose any element in arr and add or subtract a positive integer x to it. The cost of this operation is x.
Return the minimum total cost to make arr equal to brr.
Example 1:
Input: arr = [-7,9,5], brr = [7,-2,-5], k = 2
Output: 13
Explanation:
arr into two contiguous subarrays: [-7] and [9, 5] and rearrange them as [9, 5, -7], with a cost of 2.arr[0]. The array becomes [7, 5, -7]. The cost of this operation is 2.arr[1]. The array becomes [7, -2, -7]. The cost of this operation is 7.arr[2]. The array becomes [7, -2, -5]. The cost of this operation is 2.The total cost to make the arrays equal is 2 + 2 + 7 + 2 = 13.
Example 2:
Input: arr = [2,1], brr = [2,1], k = 0
Output: 0
Explanation:
Since the arrays are already equal, no operations are needed, and the total cost is 0.
Constraints:
1 <= arr.length == brr.length <= 1050 <= k <= 2 * 1010-105 <= arr[i] <= 105-105 <= brr[i] <= 105Problem Overview: You are given two arrays and a fixed operation cost. The goal is to make the arrays identical with the minimum total cost. You can either keep elements in their current order and pay the element-wise difference cost, or rearrange the arrays (with a fixed extra cost) and then align them optimally.
Approach 1: Direct Element Matching (Greedy, O(n) time, O(1) space)
The simplest strategy keeps both arrays in their original order. Iterate through the arrays and compute the total cost as sum(abs(a[i] - b[i])). This works because each position is forced to match its counterpart, so the greedy choice is simply minimizing the difference at that position. This approach avoids any rearrangement cost but may produce a higher total if the arrays are poorly aligned. Prefer this when the arrays are already similarly ordered.
Approach 2: Sort Both Arrays and Rebuild Alignment (Greedy + Sorting, O(n log n) time, O(1) extra space)
If rearranging elements is allowed with a fixed additional cost, a better strategy is to reorder both arrays to minimize pairwise differences. Sort both arrays and then compute sum(abs(sortedA[i] - sortedB[i])). Sorting ensures the smallest elements align with the smallest counterparts, which minimizes the total absolute difference. Add the fixed rearrangement cost to this value. This greedy observation comes from the property that matching numbers with similar magnitudes minimizes total deviation. The final answer is the minimum between the direct alignment cost and the sorted alignment cost plus the operation fee.
Sorting transforms the problem into a classic minimum absolute difference pairing problem. Once sorted, a single pass computes the optimal cost.
Recommended for interviews: The greedy + sorting approach is typically what interviewers expect. The direct comparison solution shows you understand the baseline cost without rearrangement. Recognizing that sorting minimizes total pairwise absolute differences demonstrates stronger algorithmic intuition with greedy reasoning and sorting. Since the arrays are processed sequentially, the implementation stays simple while maintaining an optimal O(n log n) complexity. Problems like this frequently appear in array optimization scenarios involving array transformations.
If splitting the array is not allowed, we can directly calculate the sum of absolute differences between the two arrays as the total cost c_1. If splitting is allowed, we can divide the array arr into n subarrays of length 1, then rearrange them in any order, and compare with array brr, calculating the sum of absolute differences as the total cost c_2. To minimize c_2, we can sort both arrays and then calculate the sum of absolute differences. The final result is min(c_1, c_2 + k).
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array arr.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Element Matching | O(n) | O(1) | When arrays must remain in original order or rearranging is expensive |
| Greedy + Sorting Alignment | O(n log n) | O(1) extra (in-place sort) | General case when rearranging elements is allowed and reduces total difference |
3424. Minimum Cost to Make Arrays Identical | Sorting | Arrays • Aryan Mittal • 1,155 views views
Watch 5 more video solutions →Practice Minimum Cost to Make Arrays Identical with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor