Minimum Cost to Make Array Equal

Intuitionwhy only the gaps between values matter

If the final value is t, element i must move |nums[i] - t| steps, and each step costs cost[i]. Therefore its contribution is cost[i] * |nums[i] - t|. The whole problem is choosing one target value that balances the cost of moving values from both sides toward it.

Between two consecutive values in sorted order, no input value is crossed. Moving the target through that gap changes the total cost at a constant rate: values on the left become more expensive to move, while values on the right become cheaper. The slope can change only when the target reaches an existing value, so an optimal target can be chosen from nums.

Sorting exposes those gaps. For a candidate v[i], the elements before i contribute the distance from their values up to v[i], and the elements after i contribute the distance down to v[i]. Prefix and suffix arrays store those two totals, allowing every candidate cost to be evaluated without scanning the array again.

Approach

1. 1Build pairs of value and cost before sorting, because each cost belongs permanently to its original value; sorting the two arrays independently would change the problem.
2. 2Sort the pairs by value, because then every element contributing to a candidate from the left is contiguous and every element contributing from the right is contiguous.
3. 3Build pref[i], the cost of moving all positions before i up to v[i]. Advance across each gap and multiply its width by the total cost weight already seen, because every earlier element crosses that gap once.
4. 4Build suff[i], the cost of moving all positions after i down to v[i]. Scan from right to left and multiply each gap by the total cost weight on its right, because those elements all cross the gap.
5. 5For every i, evaluate pref[i] + suff[i]. Position i itself needs no movement, and the two arrays account for every other position exactly once.
6. 6Return the smallest candidate cost, using long long for gap products and totals because even individual values and costs fit in int while their products and sums do not.

Complexitysorting dominates the running time

Annotated solutionC++ · sorted pairs with prefix and suffix costs

#include <algorithm>
#include <climits>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        int n = nums.size();
        vector<pair<int, int>> v(n);

        for (int i = 0; i < n; ++i) {
            v[i] = {nums[i], cost[i]};
        }
        sort(v.begin(), v.end());

        vector<long long> pref(n), suff(n);
        long long sumCost = 0;

        for (int i = 0; i < n; ++i) {
            long long previousValue = (i > 0 ? v[i - 1].first : 0);
            pref[i] = (i > 0 ? pref[i - 1] : 0)
                    + sumCost * (v[i].first - previousValue);
            sumCost += v[i].second;
        }

        sumCost = 0;
        for (int i = n - 1; i >= 0; --i) {
            long long nextValue = (i < n - 1 ? v[i + 1].first : 0);
            suff[i] = (i < n - 1 ? suff[i + 1] : 0)
                    + sumCost * (nextValue - v[i].first);
            sumCost += v[i].second;
        }

        long long answer = LLONG_MAX;
        for (int i = 0; i < n; ++i) {
            answer = min(answer, pref[i] + suff[i]);
        }
        return answer;
    }
};

The important detail in the prefix scan is that sumCost contains only positions strictly before i when pref[i] is computed. The gap from the previous value to v[i] is therefore charged exactly to those earlier positions. The suffix scan mirrors this: sumCost contains only positions strictly after i, so the gap is charged to the elements that must move down toward v[i].

The weighted-median alternativesame asymptotic time, less auxiliary storage

There is another way to choose the target. The total cost is a weighted absolute-distance function, so an optimal target is a weighted median: after sorting by value, choose the first value whose cumulative cost is at least half of the total cost. The prefix and suffix weights explain why: before that point, moving right does not increase the cost, and after it, moving right cannot improve the cost.

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        int n = nums.size();
        vector<pair<int, int>> v(n);
        long long totalCost = 0;

        for (int i = 0; i < n; ++i) {
            v[i] = {nums[i], cost[i]};
            totalCost += cost[i];
        }
        sort(v.begin(), v.end());

        long long seenCost = 0;
        long long target = v[0].first;
        for (const auto& [value, weight] : v) {
            seenCost += weight;
            if (seenCost * 2 >= totalCost) {
                target = value;
                break;
            }
        }

        long long answer = 0;
        for (const auto& [value, weight] : v) {
            long long distance = static_cast<long long>(value) - target;
            if (distance < 0) distance = -distance;
            answer += distance * weight;
        }
        return answer;
    }
};

This is not faster asymptotically: sorting still costs O(n log n), and evaluating the chosen target costs O(n). It is a different arrangement that buys a simpler target-selection proof and avoids the two pref and suff arrays. The sorted pair vector is still O(n) working space, while the additional storage after sorting is O(1).

Common mistakesspecific lines that change the mathematical problem