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

1
2
3
4
5
6
7
8

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

1
2
3
4
5

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 <= 10^5
  • 0 <= k <= 2 * 1010
  • -10^5 <= arr[i] <= 10^5
  • -10^5 <= brr[i] <= 10^5

Examples

Solution

Method 1 – Greedy Sorting and Direct Mapping

Intuition

To make arr equal to brr, we can rearrange contiguous subarrays of arr at a fixed cost k, and then adjust each element to match brr using add/subtract operations. The optimal way is to sort both arrays and match elements directly, as rearrangement allows any order.

Approach

  1. Sort both arr and brr.
  2. The cost to rearrange is k (if needed).
  3. For each index, calculate the cost to change arr[i] to brr[i] (absolute difference).
  4. The total cost is the sum of all element changes plus k (if rearrangement is used).
  5. If arr is already equal to brr, no rearrangement cost is needed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minimumCost(vector<int>& arr, vector<int>& brr, int k) {
        vector<int> a = arr, b = brr;
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        int ans = k;
        for (int i = 0; i < a.size(); ++i) ans += abs(a[i] - b[i]);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func minimumCost(arr, brr []int, k int) int {
    a := append([]int{}, arr...)
    b := append([]int{}, brr...)
    sort.Ints(a)
    sort.Ints(b)
    ans := k
    for i := range a {
        ans += abs(a[i] - b[i])
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minimumCost(int[] arr, int[] brr, int k) {
        int[] a = arr.clone(), b = brr.clone();
        Arrays.sort(a);
        Arrays.sort(b);
        int ans = k;
        for (int i = 0; i < a.length; ++i) ans += Math.abs(a[i] - b[i]);
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun minimumCost(arr: IntArray, brr: IntArray, k: Int): Int {
        val a = arr.sorted()
        val b = brr.sorted()
        var ans = k
        for (i in a.indices) ans += kotlin.math.abs(a[i] - b[i])
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def minimumCost(self, arr: list[int], brr: list[int], k: int) -> int:
        a = sorted(arr)
        b = sorted(brr)
        ans = k
        for x, y in zip(a, b):
            ans += abs(x - y)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn minimum_cost(arr: Vec<i32>, brr: Vec<i32>, k: i32) -> i32 {
        let mut a = arr.clone();
        let mut b = brr.clone();
        a.sort();
        b.sort();
        let mut ans = k;
        for i in 0..a.len() {
            ans += (a[i] - b[i]).abs();
        }
        ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    minimumCost(arr: number[], brr: number[], k: number): number {
        const a = [...arr].sort((x, y) => x - y);
        const b = [...brr].sort((x, y) => x - y);
        let ans = k;
        for (let i = 0; i < a.length; ++i) ans += Math.abs(a[i] - b[i]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) for sorting, where n is the length of the arrays.
  • 🧺 Space complexity: O(n) for sorting copies of the arrays.