Skip to content

3424. Minimum Cost to Make Arrays Identical

Description

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

Solutions

Solution 1: Greedy + Sorting

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 \(\textit{arr}\) into \(n\) subarrays of length 1, then rearrange them in any order, and compare with array \(\textit{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 \(\textit{arr}\).

1
2
3
4
5
6
7
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func minCost(arr []int, brr []int, k int64) int64 {
    calc := func(a, b []int) (ans int64) {
        for i := range a {
            ans += int64(abs(a[i] - b[i]))
        }
        return
    }
    c1 := calc(arr, brr)
    sort.Ints(arr)
    sort.Ints(brr)
    c2 := calc(arr, brr) + k
    return min(c1, c2)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function minCost(arr: number[], brr: number[], k: number): number {
    const calc = (a: number[], b: number[]) => {
        let ans = 0;
        for (let i = 0; i < a.length; ++i) {
            ans += Math.abs(a[i] - b[i]);
        }
        return ans;
    };
    const c1 = calc(arr, brr);
    arr.sort((a, b) => a - b);
    brr.sort((a, b) => a - b);
    const c2 = calc(arr, brr) + k;
    return Math.min(c1, c2);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn min_cost(mut arr: Vec<i32>, mut brr: Vec<i32>, k: i64) -> i64 {
        let c1: i64 = arr.iter()
            .zip(&brr)
            .map(|(a, b)| (*a - *b).abs() as i64)
            .sum();

        arr.sort_unstable();
        brr.sort_unstable();

        let c2: i64 = k + arr.iter()
            .zip(&brr)
            .map(|(a, b)| (*a - *b).abs() as i64)
            .sum::<i64>();

        c1.min(c2)
    }
}

Comments