3736. Minimum Moves to Equal Array Elements III

EasyView on LeetCode

Array Math

Time: O(n)

Space: O(1)

Problem Overview

Each move raises a single element by 1, and every element must finish on the same value.

Intuition

Each move raises a single element by 1, and every element must finish on the same value. Because values cannot fall, that shared value cannot sit below the current maximum. Raising every element past that maximum only adds extra moves for every index, including the ones that already hold the maximum. The cheapest target is therefore the maximum itself. Element i needs max minus nums[i] increments, and the total of those gaps is the maximum multiplied by the length minus the sum of the array. One pass records both the maximum and the sum, then that product minus the sum is the answer.

Algorithm

1Walk the array once.
2Keep the largest value seen and add every value into a running sum.
3Return the largest value times the length minus the sum.

Example Walkthrough

Input: nums = [2, 1, 3]

1.The maximum is 3, and the sum of the array is 6.
2.Three times the length is 9. The gaps above the values are 1, 2, and 0.
3.Nine minus 6 is 3, which raises the array to [3, 3, 3].

Output: 3

Common Pitfalls

•A target below the maximum is impossible. Values cannot be decreased.
•A target above the maximum adds the same extra move to every element. That cannot shrink the total.
•When every element is already equal, the sum equals the maximum times the length and the answer is 0.
•The formula is the total of the gaps. It does not sort the array or pick a median.

3736.cs

// Approach: Each move raises one element by 1, so the shared final value
// cannot sit below the current maximum. Raising every element to that
// maximum costs the gap for each element, which is the maximum times the
// length minus the sum of the array. One pass records both values.
// Time: O(n) Space: O(1)

public class Solution {
    public int MinMoves(int[] nums) {
        int n = nums.Length;
        int maxValue = nums[0];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int value = nums[i];
            if (value > maxValue)
                maxValue = value;
            sum += value;
        }
        return maxValue * n - sum;
    }
}

Was this solution helpful?