Skip to content

2448. Minimum Cost to Make Array Equal

Problem

You are given two 0-indexed arrays nums and cost consisting each of n positive integers.

You can do the following operation any number of times:

Increase or decrease any element of the array nums by 1.
The cost of doing one operation on the i-th element is cost[i].

Return the minimum total cost such that all the elements of the array nums become equal.

Example 1:

Input: nums = [1,3,5,2], cost = [2,3,1,14]
Output: 8
Explanation: We can make all the elements equal to 2 in the following way:

- Increase the 0th element one time. The cost is 2.
- Decrease the 1st element one time. The cost is 3.
- Decrease the 2nd element three times. The cost is 1 + 1 + 1 = 3.
The total cost is 2 + 3 + 3 = 8.
It can be shown that we cannot make the array equal with a smaller cost.

Example 2:

Input: nums = [2,2,2,2,2], cost = [4,2,8,1,3]
Output: 0
Explanation: All the elements are already equal, so no operations are needed.

Constraints:

  • n == nums.length == cost.length
  • 1 <= n <= 105
  • 1 <= nums[i], cost[i] <= 106

Solution

Overview

  1. Assuming result always try to match one of the number inside the array
    - It easy to conclude that the equal value that we trying to find in in between min - max of the array (or else they are the min or max of the array)
    - We can just using binary search if the assumption isn’t true, with left and right start at min - max

  2. If you can calculate the cost given a specific equal value it in O(1) time. The handling process rely on the fact that if you can separating all the increase / decrease part of the array, with each change quickly or not.

    • After sorting the provided nums, which cost O(n log n)
    • We can separating increase / decrease part in half by O(1) if we tryout each nums in sorted order; or O(log n) in-case we using binary search
    • Then the problem becoming O(n) to tryout all nums; or O(log (max - min)) in-case we using binary search
    • We can achieve O(1) time complexity calculate the cost given a specific equal value this by just pre-calculating all array range with Dynamic Programming Sub array-Sum
    • Overall, a O(n log n) + O(n)*O(1) or O(n log n) + O(log n)* O(log (max - min)) *O(1)

Implement

O(n log n) + O(n)*O(1)

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        arr = list(zip(nums, cost))
        arr.sort()
        sumCost = [0] * len(arr)
        for i, (_, cost) in enumerate(arr):
            sumCost[i] += cost
            if i > 0:
                sumCost[i] += sumCost[i-1]

        def sumRange(sumCost, left, right):
            if left == -1:
                return sumCost[right]
            return sumCost[right] - sumCost[left]

        minNums = min(nums)
        res = [0] * len(arr)
        res[0] = sum([(num - minNums) * cost for num, cost in arr])

        for i in range(1, len(arr)):
            preNum, preCost = arr[i-1]
            num, cost = arr[i]
            res[i] = res[i - 1]
            res[i] += sumRange(sumCost, -1, i-1) * (-preNum + num)
            res[i] -= sumRange(sumCost, i-1, len(arr) - 1) * (num - preNum)

        return min(res)

O(n log n) + O(log n)* O(log (max - min)) *O(1) (WRONG - FIRST THOUGHT THO)

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        arr = list(zip(nums, cost))
        arr.sort()
        sumCost = [0] * len(arr)
        for i, (_, cost) in enumerate(arr):
            sumCost[i] += cost
            if i > 0:
                sumCost[i] += sumCost[i-1]

        def sumRange(sumCost, left, right):
            if left == -1:
                return sumCost[right]
            return sumCost[right] - sumCost[left]

        minNums = min(nums)
        exampleRes = sum([(num - minNums) * cost for num, cost in arr])

        def findCut(arr, value):
            left = -1
            right = len(arr)
            while True:
                mid = (left + right)// 2
                if left == mid:
                    break
                if arr[mid] <= value:
                    left = mid
                else:
                    right = mid
            return right

        maxNums = max(nums)
        left = minNums-1
        right = maxNums+1
        while True:
            mid = (left + right)// 2
            cutIndex = findCut(arr, mid)
            testRes = exampleRes
            testRes += sumRange(sumCost, -1, cutIndex) * (num - minNums)
            testRes -= sumRange(sumCost, cutIndex, len(arr) - 1) * (num -  minNums)

        return min(res)
Last update : October 13, 2023
Created : August 16, 2023