We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Make Arrays Identical

Number: 3712

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two integer arrays arr and brr of the same length and an integer k, you can perform two types of operations on arr:

  1. Split arr into any number of contiguous subarrays and rearrange these subarrays in any order at a fixed cost of k.
  2. For any element in arr, you can add or subtract a positive integer x from it at a cost equal to x. The goal is to transform arr into brr with minimum total cost.

Key Insights

  • You can rearrange arr arbitrarily (by splitting into single-element subarrays) at a fixed cost k.
  • Without the rearrangement operation, you must match each arr[i] with brr[i], giving a cost of sum|arr[i] - brr[i]|.
  • With one rearrangement operation, you can optimally pair elements by sorting both arrays and then calculating the total absolute differences.
  • The answer is the minimum between not reordering at all and paying the individual modification cost, versus paying k plus the minimal cost obtained by matching sorted arrays.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting when rearrangement is considered. Space Complexity: O(n) for storing the sorted arrays.

Solution

The problem has two clear strategies. In the first strategy, you do not perform any rearrangement, and the cost is simply the sum of absolute differences between arr[i] and brr[i]. In the second strategy, you perform one rearrangement operation, which allows you to match elements optimally by pairing the smallest with the smallest, the second smallest with the second smallest, etc. In that case, the cost is k plus the sum of absolute differences between sorted arr and sorted brr. Simply choose the strategy that gives the minimum total cost.

Data structures and algorithmic tools used:

  • Sorting is used to find the optimal pairing for the rearrangement strategy.
  • A simple linear pass is used to calculate the sum of absolute differences. The key "gotcha" is to realize that even though the rearrangement operation does not allow arbitrary permutation for free, splitting arr into one-element subarrays effectively permits any permutation at a fixed cost of k.

Code Solutions

# Python solution with detailed comments

def minCostToMakeIdentical(arr, brr, k):
    # First strategy: no rearrangement, sum absolute differences at corresponding indices.
    cost_no_rearrange = sum(abs(a - b) for a, b in zip(arr, brr))
    
    # Second strategy: rearrangement operation once at cost k,
    # then cost is sum of absolute differences after sorting both arrays.
    sorted_arr = sorted(arr)
    sorted_brr = sorted(brr)
    cost_rearrange = k + sum(abs(a - b) for a, b in zip(sorted_arr, sorted_brr))
    
    # Return the minimum cost between the two strategies.
    return min(cost_no_rearrange, cost_rearrange)

# Example usage
arr = [-7, 9, 5]
brr = [7, -2, -5]
k = 2
print(minCostToMakeIdentical(arr, brr, k))  # Expected output: 13
← Back to All Questions