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 Array Equal

Number: 2538

Difficulty: Hard

Paid? No

Companies: HashedIn, Google, Amazon, Cisco

Problem Description

We are given two 0-indexed arrays, nums and cost, both of length n. We can increase or decrease any element in nums by 1 with a corresponding cost given in cost. We need to return the minimum total cost required to make every element of nums equal.

Key Insights

  • The problem can be reframed as choosing an optimal target value such that the weighted cost (using the cost array as weights) of moving each nums[i] to this target is minimized.
  • This optimal target is the weighted median of the nums values, considering the weights provided by the cost array.
  • Sorting the elements along with their associated costs makes it straightforward to compute a cumulative weight and identify the point where the cumulative weight crosses half of the total.
  • Once the weighted median is determined, computing the total cost is a matter of summing the absolute differences multiplied by the respective cost for each element.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) to store paired values (nums and cost).

Solution

The idea is to:

  1. Pair each element in nums with its corresponding cost.
  2. Sort these pairs by the value of nums.
  3. Compute the total cost weight (sum of the cost array).
  4. Traverse through the sorted pairs to find the weighted median, i.e. the point where the cumulative cost becomes at least half of the total.
  5. Calculate the total cost required by summing up cost[i] * |nums[i] - median| for all i.

This approach efficiently computes the minimum cost with the weighted median serving as the optimal target value for all numbers.

Code Solutions

# Define the class with the solution method
class Solution:
    def minCost(self, nums, cost):
        # Pair each number with its corresponding cost and sort them by number
        pairs = sorted(zip(nums, cost))
        total_weight = sum(cost)  # Total cumulative cost weight
        cumulative = 0
        median = 0
        
        # Find the weighted median
        for num, c in pairs:
            cumulative += c
            # Using (total_weight + 1) // 2 to handle both even and odd totals
            if cumulative >= (total_weight + 1) // 2:
                median = num
                break
                
        # Calculate the minimum total cost to make the array equal to the median
        total_cost = 0
        for num, c in pairs:
            total_cost += abs(num - median) * c
        return total_cost

# Example usage:
# sol = Solution()
# print(sol.minCost([1,3,5,2], [2,3,1,14]))  # Output: 8
← Back to All Questions