Minimum Cost to Equalize Array

Start by evaluating potential target values for the array using a greedy approach, ensuring all choices maintain the invariant of minimum total cost. Consider each operation cost carefully and sum contributions for each candidate. This method guarantees an efficient determination of the least cost to equalize all elements in the array.

Problem Statement

You are given an integer array nums and two operation costs, cost1 and cost2. You may repeatedly apply either operation to any element, increasing or decreasing its value by one according to cost1 or cost2.

Determine the minimum total cost required to make all elements in nums equal. Since the total cost can be very large, return it modulo 10^9 + 7.

Examples

Example 1

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

Output: 15

The following operations can be performed to make the values equal: The total cost is 15.

Example 2

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

Output: 6

The following operations can be performed to make the values equal: The total cost is 6.

Example 3

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

Output: 4

The following operations can be performed to make the values equal: The total cost is 4.

Constraints

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106
• 1 <= cost1 <= 106
• 1 <= cost2 <= 106

Solution Approach

Greedy Target Selection

Sort the array and consider each element as a candidate target. Compute the cost to convert all other elements to this value using the provided operations. The optimal target minimizes total cost due to greedy accumulation.

Cost Accumulation Using Prefix Sums

Maintain prefix sums of both array values and their associated costs. For each candidate target, calculate left and right contributions efficiently. This reduces redundant calculations and speeds up evaluation for large arrays.

Invariant Validation and Modulo Application

After computing each total cost, check that the greedy invariant holds: no other candidate target offers a smaller cost. Apply modulo 10^9 + 7 to the final answer to meet the constraints and handle large numbers.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is dominated by sorting and evaluating each candidate target, roughly O(n log n) for sorting plus O(n) for prefix sum evaluation. Space complexity is O(n) for storing prefix sums and intermediate calculations.

What Interviewers Usually Probe

• They may ask if your approach always finds the minimal cost or if edge cases could violate the greedy assumption.
• Expect questions on optimizing calculations for large arrays to avoid TLE with naive nested loops.
• Clarify how prefix sums and invariants interact to maintain correctness while reducing runtime.

Common Pitfalls or Variants

Common pitfalls

• Failing to consider both operation costs correctly when computing conversion costs for each element.
• Neglecting modulo 10^9 + 7 leading to integer overflow in languages with fixed-size integers.
• Assuming the array's median is always optimal without verifying against operation cost differences.

Follow-up variants

• Minimizing cost when each element has a distinct cost function for increments and decrements.
• Extending the problem to two-dimensional grids where each cell can be equalized with row and column operations.
• Calculating minimum cost with fractional increments or continuous values rather than integer steps.

FAQ

What is the main pattern used in Minimum Cost to Equalize Array?

The primary pattern is greedy choice plus invariant validation, selecting candidate targets and ensuring minimal total cost.

Why is prefix sum useful in this problem?

Prefix sums allow quick computation of cumulative costs for left and right segments, reducing redundant calculations for each target.

Do I always pick the median as the target value?

Not necessarily; the optimal target depends on operation costs cost1 and cost2, so evaluate all candidates using greedy accumulation.

How does modulo 10^9 + 7 affect calculations?

It prevents integer overflow by keeping totals within bounds and should be applied after each full total cost computation.

Can GhostInterview help with edge cases?

Yes, it simulates different array configurations and validates that the greedy invariant holds for each candidate target.