Minimum Moves to Equal Array Elements II (Leetcode 462)

Difficulty: Medium Link: Day 19:May Leetcode Challenge

Problem Description

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Examples

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]
Input: nums = [1,10,2,9]
Output: 16

Constraints

  • n == nums.length
  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Solution

One brute force approach can be to consider every element as the pivot and count the number of aways to make other elements equal to the pivot. We can track the minimum of those moves and this would be our answer. We would need two nested loops for checking every combination of numbers with the pivot, so it would be a solution bounded by O(N2). Can we do something better?

Sorting

If we arrange the values in ascending order and plot it on a histogram, we can notice that moves needed is the absolute difference between the peaks. If the moves cover the mid-way, then the total moves would be minimum. The values on the left of mid value are lesser and all values on the right are greater. This middle value has a special name in the statistics ,called the “median”. This is the middle values in the sorted list.

We can easily find the median by sorting the array and finding the middle value. Then we can find the sum of absolute difference with the median in a single iteration.

Swift

class Solution {
func minMoves2(_ nums: [Int]) -> Int {
let nums = nums.sorted()
let median = nums[nums.count/2]
var moves = 0
for num in nums{
moves += abs(median num)
}
return moves
}
}

Java

public class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int num : nums) {
sum += Math.abs(nums[nums.length / 2] num);
}
return sum;
}
}

Python

def minMoves2(self, nums: List[int]) -> int:
median = sorted(nums)[len(nums) // 2]
return sum(abs(num median) for num in nums)

Complexity Analysis

Time = O(NLogN)

Space = O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *