Minimum cost to make arrays identical

Array Greedy Sorting

37.7% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(arr: Vec<i32>, brr: Vec<i32>, k: i64) -> i64 {
    let cost_no: i64 = arr.iter().zip(brr.iter())
      .map(|(&a, &b)| (a as i64 - b as i64).abs()).sum();
    let mut sa = arr.clone();
    let mut sb = brr.clone();
    sa.sort();
    sb.sort();
    let cost_re: i64 = k + sa.iter().zip(sb.iter())
      .map(|(&a, &b)| (a as i64 - b as i64).abs()).sum::<i64>();
    cost_no.min(cost_re)
  }
}