# Minimum Cost to Make Arrays Identical
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-cost-to-make-arrays-identical)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-make-arrays-identical
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Dynamic Programming Approach
A brute-force approach can be formulated using dynamic programming. The idea is to build a solution for the whole array by solving it for prefixes. We can define `dp[i]` as the minimum cost to make the first `i` elements of `arr` equal to the first `i` elements of `brr`. To compute `dp[i]`, we consider all possible ways the last contiguous block `arr[j...i-1]` is formed and matched with `brr[j...i-1]`. This involves calculating the cost for this segment (either with or without rearrangement) and adding it to the optimal cost for the prefix `arr[0...j-1]`. This approach systematically explores all partitions of the array into blocks.
**Time:** O(N^2 * N log N) or O(N^3) depending on the specific DP formulation. This is because for each state `dp[i]`, we iterate through `j`, and for each segment `[j, i-1]`, we might need to sort, which takes `O((i-j)log(i-j))` time. · **Space:** O(N) or O(N^2) depending on the DP state.
**Pros:** It's a systematic way to explore the problem space, breaking it down into smaller subproblems.
**Cons:** The time complexity is very high, making it impractical for the given constraints.; The DP formulation is complex and easy to get wrong, especially in handling the one-time cost `k`.
### Explanation
This approach attempts to solve the problem by breaking it down into subproblems concerning prefixes of the arrays. Let's define `dp[i]` as the minimum cost to make `arr[0...i-1]` equal to `brr[0...i-1]`. The transition to compute `dp[i]` would involve considering all possible split points `j < i`, where `arr[j...i-1]` forms the last block in the prefix of length `i`.

The cost for this last block, `cost(j, i)`, is the minimum of two scenarios:
1.  Matching `arr[j...i-1]` to `brr[j...i-1]` without rearrangement: `sum_{t=j}^{i-1} |arr[t] - brr[t]|`.
2.  Matching `arr[j...i-1]` to `brr[j...i-1]` with rearrangement: `k + sum(|sorted(arr[j...i-1])[t] - sorted(brr[j...i-1])[t]|)`.

The DP recurrence would be `dp[i] = min_{0 <= j < i} (dp[j] + cost(j, i))`. However, a major flaw in this simple DP is that the rearrangement cost `k` is global. A correct DP would need to track whether the rearrangement operation has been used, for instance, with a state `dp[i][state]`, making the logic more convoluted and the computation even slower.

For example, a valid (but slow) DP could be:
`dp[i][0]` = min cost for prefix `i` without using rearrangement.
`dp[i][1]` = min cost for prefix `i` after using rearrangement.

`dp[i][0] = dp[i-1][0] + |arr[i-1] - brr[i-1]|`
`dp[i][1] = min(dp[i-1][1] + cost_rearranged_for_one_element, dp[0][0] + k + cost_rearranged_for_prefix_i)`
This gets very complex. A simpler to state, but still slow, version is the `O(N^3 log N)` DP:
```java
// This is a conceptual illustration of a slow DP and not a complete, correct solution.
// A correct DP is significantly more complex to formulate.
long[] dp = new long[n + 1];
Arrays.fill(dp, Long.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j < i; j++) {
        // Cost for segment arr[j..i-1] and brr[j..i-1]
        long noRearrangeCost = 0;
        for (int l = j; l < i; l++) {
            noRearrangeCost += Math.abs(arr[l] - brr[l]);
        }

        int[] subArr = Arrays.copyOfRange(arr, j, i);
        int[] subBrr = Arrays.copyOfRange(brr, j, i);
        Arrays.sort(subArr);
        Arrays.sort(subBrr);
        long rearrangeModCost = 0;
        for (int l = 0; l < subArr.length; l++) {
            rearrangeModCost += Math.abs(subArr[l] - subBrr[l]);
        }
        // This DP logic is flawed as k is paid once.
        // A correct version would be much more complex.
        // dp[i] = Math.min(dp[i], dp[j] + noRearrangeCost);
        // dp[i] = Math.min(dp[i], dp[j] + k + rearrangeModCost);
    }
}
```
### Algorithm
1. Define a DP state `dp[i]` as the minimum cost to make the prefix `arr[0...i-1]` identical to `brr[0...i-1]`.
2. To compute `dp[i]`, we iterate through all possible split points `j` from `0` to `i-1`. The segment `[j, i-1]` is treated as the last block.
3. For each segment `arr[j...i-1]`, we calculate the cost to make it identical to `brr[j...i-1]`. This cost itself has two possibilities:
    a. **No rearrangement for this block**: The cost is the sum of absolute differences: `sum_{t=j}^{i-1} |arr[t] - brr[t]|`.
    b. **Rearrangement for this block**: The cost involves the rearrangement penalty `k` plus the minimum modification cost. The minimum modification cost for two arrays of numbers where one can be permuted is obtained by sorting both and summing the absolute differences: `k + sum(|sorted(arr[j...i-1])[t] - sorted(brr[j...i-1])[t]|)`.
4. The DP transition would look something like `dp[i] = min_{0 <= j < i} (dp[j] + cost_for_segment(j, i-1))`. However, this is flawed because the cost `k` is paid only once for the entire array, not per block. A more complex DP state is needed, like `dp[i][0]` (cost for prefix `i` without using rearrangement) and `dp[i][1]` (cost for prefix `i` having used rearrangement), leading to a more complex set of transitions.
5. The base case would be `dp[0] = 0`.
6. The final answer would be `dp[n]` (or `min(dp[n][0], dp[n][1])` for the more complex state).

## Optimal Approach via Sorting
A much more efficient approach comes from a key insight into the rearrangement operation. The problem offers two fundamental choices: either modify the array in place or pay a fixed cost `k` to rearrange and then modify. The crucial observation is that the rearrangement operation allows for any permutation of `arr`'s elements. This is because we can choose to split `arr` into `n` subarrays, each containing a single element. These can then be rearranged in any order. With this understanding, the problem simplifies to comparing two costs: the cost of in-place modification versus the cost of optimal rearrangement plus modification.
**Time:** O(N log N), dominated by the sorting of the two arrays. The rest of the calculations (summing differences) take O(N) time. · **Space:** O(N) for storing the copies of the arrays for sorting. If in-place sorting is allowed, it can be O(log N) or O(1) depending on the sort implementation's space usage.
**Pros:** Highly efficient with a time complexity of O(N log N).; Simple to understand and implement once the key insight is made.; Correctly handles all cases and fits within the given constraints.
**Cons:** The main challenge is realizing the simplification. The problem wording about 'contiguous subarrays' can be misleading and might cause one to over-engineer a more complex solution.
### Explanation
This approach correctly identifies that we only need to compare two distinct scenarios.

**Scenario 1: No Rearrangement**
If we don't perform the rearrangement operation, we must make `arr[i]` equal to `brr[i]` for every index `i`. The cost for this is the sum of the absolute differences between corresponding elements.
`cost_no_rearrange = sum_{i=0}^{n-1} |arr[i] - brr[i]|`

**Scenario 2: With Rearrangement**
If we choose to perform the rearrangement operation, we incur a fixed cost of `k`. The operation allows us to split `arr` into any number of contiguous subarrays and then reorder these subarrays. A powerful application of this is to split `arr` into `n` subarrays of length 1. This effectively allows us to rearrange the elements of `arr` into any permutation we desire.

To minimize the total cost in this scenario, we need to find the permutation of `arr`, let's call it `arr'`, that minimizes the subsequent modification cost, which is `sum(|arr'[i] - brr[i]|)`. It is a well-known result that for two collections of numbers, the sum of absolute differences is minimized when both are sorted and matched element by element. Therefore, the minimum possible modification cost is achieved by matching the sorted version of `arr` with the sorted version of `brr`.

`min_modification_cost = sum_{i=0}^{n-1} |sorted(arr)[i] - sorted(brr)[i]|`

The total cost for this scenario is:
`cost_rearrange = k + min_modification_cost`

**Final Answer**
The minimum total cost is the lesser of the costs from these two scenarios.
`min_total_cost = min(cost_no_rearrange, cost_rearrange)`

The implementation involves calculating these two costs and returning the minimum. This requires sorting both arrays, which dominates the time complexity.

```java
import java.util.Arrays;

class Solution {
    public long minCost(int[] arr, int[] brr, int k) {
        int n = arr.length;

        // Scenario 1: No rearrangement
        long cost1 = 0;
        for (int i = 0; i < n; i++) {
            cost1 += Math.abs(arr[i] - brr[i]);
        }

        // Scenario 2: With rearrangement
        // Create copies to not modify the original arrays if they are needed elsewhere
        int[] sortedArr = Arrays.copyOf(arr, n);
        int[] sortedBrr = Arrays.copyOf(brr, n);

        Arrays.sort(sortedArr);
        Arrays.sort(sortedBrr);

        long minModificationCost = 0;
        for (int i = 0; i < n; i++) {
            minModificationCost += Math.abs(sortedArr[i] - sortedBrr[i]);
        }

        long cost2 = (long)k + minModificationCost;

        return Math.min(cost1, cost2);
    }
}
```
### Algorithm
1.  Recognize there are two main scenarios to compare:
    a. Make `arr` equal to `brr` without using the rearrangement operation.
    b. Use the rearrangement operation (paying cost `k`) and then perform modifications.
2.  Calculate the cost for the first scenario (`cost1`). This is a simple element-wise sum of absolute differences: `cost1 = sum(|arr[i] - brr[i]|)` for all `i` from `0` to `n-1`.
3.  Calculate the cost for the second scenario (`cost2`).
    a. The rearrangement operation costs `k`. It allows splitting `arr` into any number of contiguous subarrays and reordering them. By splitting `arr` into `n` subarrays of size 1, we can achieve any permutation of `arr`'s elements.
    b. The goal is to find the permutation of `arr`, let's call it `arr'`, that minimizes the modification cost `sum(|arr'[i] - brr[i]|)`.
    c. It's a standard result that this sum is minimized when the elements of `arr` are matched with elements of `brr` in sorted order. That is, the `i`-th smallest element of `arr` is matched with the `i`-th smallest element of `brr`.
    d. Therefore, the minimum modification cost after rearrangement is `sum(|sorted(arr)[i] - sorted(brr)[i]|)`.
    e. The total cost for the second scenario is `cost2 = k + sum(|sorted(arr)[i] - sorted(brr)[i]|)`.
4.  The final answer is the minimum of the costs from the two scenarios: `min(cost1, cost2)`.

# Solutions
### Java

```java
class Solution {
public
  long minCost(int[] arr, int[] brr, long k) {
    long c1 = calc(arr, brr);
    Arrays.sort(arr);
    Arrays.sort(brr);
    long c2 = calc(arr, brr) + k;
    return Math.min(c1, c2);
  }
private
  long calc(int[] arr, int[] brr) {
    long ans = 0;
    for (int i = 0; i < arr.length; ++i) {
      ans += Math.abs(arr[i] - brr[i]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minCost(vector<int> &arr, vector<int> &brr, long long k) {
    auto calc = [&](vector<int> &arr, vector<int> &brr) {
      long long ans = 0;
      for (int i = 0; i < arr.size(); ++i) {
        ans += abs(arr[i] - brr[i]);
      }
      return ans;
    };
    long long c1 = calc(arr, brr);
    ranges ::sort(arr);
    ranges ::sort(brr);
    long long c2 = calc(arr, brr) + k;
    return min(c1, c2);
  }
};

```

### Python

```python
class Solution:
    def minCost(self, arr: List[int], brr: List[int], k: int) -> int: c1 = sum(abs(a - b) for a, b in zip(arr, brr)) arr . sort() brr . sort() c2 = k + sum(abs(a - b) for a, b in zip(arr, brr)) return min(c1, c2)

```