Minimum Cost to Make Arrays Identical
Source: leetcode
Difficulty: Medium
Tags: array, greedy, sorting

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:


- Split `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:**


- Split `arr` into two contiguous subarrays: `[-7]` and `[9, 5]` and rearrange them as `[9, 5, -7]`, with a cost of 2\.
- Subtract 2 from element `arr[0]`. The array becomes `[7, 5, -7]`. The cost of this operation is 2\.
- Subtract 7 from element `arr[1]`. The array becomes `[7, -2, -7]`. The cost of this operation is 7\.
- Add 2 to element `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 <= 105`
- `0 <= k <= 2 * 1010`
- `-105 <= arr[i] <= 105`
- `-105 <= brr[i] <= 105`




C++ solution:
class Solution {
public:
    long long minCost(vector<int>& arr, vector<int>& brr, long long k) {
        int n = arr.size();
        long long costNoReorder = 0;
        for (int i = 0; i < n; i++) {
            costNoReorder += llabs((long long)arr[i] - (long long)brr[i]);
        }
        vector<int> arrSorted = arr, brrSorted = brr;
        sort(arrSorted.begin(), arrSorted.end());
        sort(brrSorted.begin(), brrSorted.end());
        long long costReorderAdjust = 0;
        for (int i = 0; i < n; i++) {
            costReorderAdjust += llabs((long long)arrSorted[i] - (long long)brrSorted[i]);
        }
        long long costReorder = k + costReorderAdjust;
        return costNoReorder < costReorder ? costNoReorder : costReorder;
    }
};

Go solution:
func minCost(arr []int, brr []int, k int64) int64 {
	n := len(arr)
	var costNoReorder int64
	for i := 0; i < n; i++ {
		diff := int64(arr[i]) - int64(brr[i])
		if diff < 0 {
			diff = -diff
		}
		costNoReorder += diff
	}
	arrCopy := make([]int, n)
	copy(arrCopy, arr)
	brrCopy := make([]int, n)
	copy(brrCopy, brr)
	sort.Ints(arrCopy)
	sort.Ints(brrCopy)
	var costReorder int64 = k
	for i := 0; i < n; i++ {
		diff := int64(arrCopy[i]) - int64(brrCopy[i])
		if diff < 0 {
			diff = -diff
		}
		costReorder += diff
	}
	if costNoReorder < costReorder {
		return costNoReorder
	}
	return costReorder
}

Java solution:
class Solution {
    public long minCost(int[] arr, int[] brr, long k) {
        int n = arr.length;
        long costNo = 0;
        for (int i = 0; i < n; i++) {
            costNo += Math.abs((long)arr[i] - (long)brr[i]);
        }
        int[] sortedArr = arr.clone();
        int[] sortedBrr = brr.clone();
        java.util.Arrays.sort(sortedArr);
        java.util.Arrays.sort(sortedBrr);
        long costSorted = 0;
        for (int i = 0; i < n; i++) {
            costSorted += Math.abs((long)sortedArr[i] - (long)sortedBrr[i]);
        }
        return Math.min(costNo, k + costSorted);
    }
}

JavaScript solution:
var minCost = function(arr, brr, k) {
    const n = arr.length;
    let costNoReorder = 0;
    for (let i = 0; i < n; i++) {
        costNoReorder += Math.abs(arr[i] - brr[i]);
    }
    let arrSorted = arr.slice().sort((a, b) => a - b);
    let brrSorted = brr.slice().sort((a, b) => a - b);
    let costReorderAdjust = 0;
    for (let i = 0; i < n; i++) {
        costReorderAdjust += Math.abs(arrSorted[i] - brrSorted[i]);
    }
    let costReorder = k + costReorderAdjust;
    return Math.min(costNoReorder, costReorder);
};

Python solution:
class Solution:
    def minCost(self, arr: List[int], brr: List[int], k: int) -> int:
        n = len(arr)
        direct_cost = sum(abs(a - b) for a, b in zip(arr, brr))
        sorted_arr = sorted(arr)
        sorted_brr = sorted(brr)
        reorder_cost = k + sum(abs(a - b) for a, b in zip(sorted_arr, sorted_brr))
        return min(direct_cost, reorder_cost)

Ruby solution:
def min_cost(arr, brr, k)
  cost_no_reorder = arr.zip(brr).sum { |a, b| (a - b).abs }
  cost_reorder = k + arr.sort.zip(brr.sort).sum { |a, b| (a - b).abs }
  [cost_no_reorder, cost_reorder].min
end