Leetcode 462. Minimum Moves to Equal Array Elements II

Accepted Code

Problem Statement

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.

Test cases are designed so that the answer will fit in a 32-bit integer.

Test Cases

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

Constraints

  • n == nums.length
  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Approach

Our aim is to make all elements equal with the minimum number of possible moves. If we don’t care about the minimum, then we can just fix 1 element and make all other element equal to this fixed element by doing increment or decrement whatever. But this will not guarantee the minimum and this is not the case we are looking for.

We need to make the array elements equal + we need to do it in the minimum number of moves possible.
First of all, we need to sort the elements and try to make all elements equal to the median element. All the elements from the left needs to be incremented and all the elements from the right needs to be decremented. So if we choose any number other than the median as our fixed number, then the number of moves will be higher. So our idea is simple, just sort the array and take the moves from left and right elements to be equal to the median.

In the problem statement, we are given we can only increment or decrement an element by 1.
So if we consider the right element, ie nums[right], we need
possibleMovesFromRight= nums[right] — nums[middle] to make nums[right] = nums[middle].

If we consider the left element, ie nums[left], we need
possibleMovesFromLeft = nums[middle] — nums[left] to make nums[left] = nums[middle].

So the total amount of moves required will be :

totalMoves = possibleMovesFromRight + possibleMovesFromLeft
= nums[right] — nums[middle] + nums[middle] — nums[left]
= nums[right] — nums[left].

Algorithm

  1. Sort the given array.
  2. Take 2 pointers left and right.
  3. Traverse while left < right.
  4. Track moves = nums[right] — nums[left].
  5. Increment left and decrement right.
  6. Return moves.

Time and Space Complexity

We are sorting the array and traversing through the array after sorting.
So our time complexity will be O(nlogn + n) where n = length of array.

We didn’t make use of any extra space, so space complexity = O(1).

Code

Java Code

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rohith Vazhathody

Rohith Vazhathody

Software Engineer | Weekly articles | Interested in DSA, design | Writes about problem solving, algorithm explanation of my understanding and Java Codes.