Skip to content

3424. Minimum Cost to Make Arrays Identical 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  long long minCost(vector<int>& arr, vector<int>& brr, long long k) {
    return min(noSortCost(arr, brr), sortCost(arr, brr) + k);
  }

 private:
  long long noSortCost(const vector<int>& arr, const vector<int>& brr) {
    long res = 0;
    for (int i = 0; i < arr.size(); ++i)
      res += abs(arr[i] - brr[i]);
    return res;
  }

  long long sortCost(vector<int>& arr, vector<int>& brr) {
    ranges::sort(arr);
    ranges::sort(brr);
    long res = 0;
    for (int i = 0; i < arr.size(); ++i)
      res += abs(arr[i] - brr[i]);
    return res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public long minCost(int[] arr, int[] brr, long k) {
    return Math.min(noSortCost(arr, brr), sortCost(arr, brr) + k);
  }

  private long noSortCost(int[] arr, int[] brr) {
    long res = 0;
    for (int i = 0; i < arr.length; ++i)
      res += Math.abs(arr[i] - brr[i]);
    return res;
  }

  private long sortCost(int[] arr, int[] brr) {
    Arrays.sort(arr);
    Arrays.sort(brr);
    long res = 0;
    for (int i = 0; i < arr.length; ++i)
      res += Math.abs(arr[i] - brr[i]);
    return res;
  }
}

1
2
3
4
5
class Solution:
  def minCost(self, arr: list[int], brr: list[int], k: int) -> int:
    def cost(arr: list[int], brr: list[int]) -> int:
      return sum(abs(a - b) for a, b in zip(arr, brr))
    return min(cost(arr, brr), cost(sorted(arr), sorted(brr)) + k)