Minimum Moves to Equal Array Elements II — LeetCode 462 Python Solution

The problem

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.

Example

Input

nums = [1,2,3]

Output

2

Explanation

Only two moves are needed (remember each move increments or decrements one element):

Python solution

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        k = nums[len(nums) >> 1]
        return sum(abs(v - k) for v in nums)

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 462. Minimum Moves to Equal Array Elements II is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems