← leetcode

Minimum Moves to Equal Array Elements II

· Medium

LeetCode problem 462

very similar problem to yesterday's. after actually thinking this time, i came to the realisation that the goal value to move array elements to was just the median value.

this is because you want a balanced number of array elements incrementing and decrementing: raising the goal value by 1 costs one more move for every element below it, but saves one move for every element above it, so the total keeps dropping until there are as many elements above the goal value as below it.

code link to code

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n{static_cast<int>(nums.size())};

        // even if `n` is even, it costs the same whether it's `nums[n/2]` or `nums[n/2 - 1]`
        int median{nums[n/2]};
        int ans{};

        for (int num : nums) {
            ans += abs(num - median);
        }

        return ans;
    }
};

complexity link to complexity

  • Time: O(n log(n))
  • Space: O(1)

time taken link to time taken

  • 5 minutes and 36 seconds