Algorithms to Make List Values Equal

You are given a list of integers nums. Consider an operation where we select some subset of integers in the list and increment all of them by one. Return the minimum number of operations needed to make all values in the list equal to each other.

Constraints
1 ≤ n ≤ 100,000 where n is the length of nums
0 ≤ nums[i] ≤ 10**9 for all 0 ≤ i < n
Example 1
Input
nums = [1, 3, 0]
Output
3
Explanation
The 3 operations we can take are:
Increment [1, 0] to get [2, 3, 1]
Increment [2, 1] to get [3, 3, 2]
Increment [2] to get [3, 3, 3]

Making List Values Equal

Because we can choose any sublist – thus if we sort the numbers, it doesn’t matter (picking sequence). After sorting the array, we can then pick the neighour numbers and the cost would be the difference. Then if we accumulate them that will be the minimum number of operations that is required to make all numbers in the list equal to each other.

1
2
3
4
5
6
7
8

int makeListEqual(vector<int>& nums) {
    sort(begin(nums), end(nums));
    int ans = 0;
    for (int i = 0; i + 1 < nums.size(); ++ i) {
        ans += nums[i + 1] - nums[i];
    }
    return ans;
}

int makeListEqual(vector<int>& nums) {
    sort(begin(nums), end(nums));
    int ans = 0;
    for (int i = 0; i + 1 < nums.size(); ++ i) {
        ans += nums[i + 1] - nums[i];
    }
    return ans;
}

The time complexity is O(NLogN) as we are sorting. The space complexity is O(1).

Another more efficient algorithm would be to compute the minimum and maximum values of the array, and the difference will be the minimum number of the operations.

1
2
3
4

int makeListEqual(vector<int>& nums) {
    auto minmax = minmax_element(begin(nums), end(nums));
    return *minmax.second - *minmax.first;
}

int makeListEqual(vector<int>& nums) {
    auto minmax = minmax_element(begin(nums), end(nums));
    return *minmax.second - *minmax.first;
}

The time complexity is O(N). The space complexity is O(1). We use minmax_element to compute the min and max values in the array.

–EOF (The Ultimate Computing & Technology Blog) —