Watch 6 video solutions for Minimum Cost to Make Arrays Identical, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Aryan Mittal has 1,155 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |