462. Minimum Moves to Equal Array Elements II

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.

Constraints

• n == nums.length

• 1 <= nums.length <= 105

• -109 <= nums[i] <= 109

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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]

Example 2

Input: nums = [1, 10, 2, 9]

Output: 16

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int minMoves2(int[] nums) {
        if(nums == null || nums.length <= 1) {
            return 0;
        }
        Arrays.sort(nums);
        int moves = 0, median = nums[nums.length/2];
        for(int num: nums) {
            moves += Math.abs(num-median);
        }
        return moves;
    }
}

Follow up