As we are incrementing and decrementing elements one-by-one, the least amount of moves should be acquired through converging the largest and the smallest values to some middle value, namely the median.
We can find the median of the array trivially by sorting it and checking its middle element. We can also utilize the quicksort algorithm explained below.
Beyond just finding the median, one can also consider how much the largest and the smallest value in the need to be decremented or incremented to have them converge to some value. If the largest is b and the smallest is a, moving both of them to c would cost b-c + c-a = b-a. We can sort the array and use this for every larger and smaller element as we converge into the middle.
Quickselect
Quickselect is an algorithm used for finding the kth smallest element in an unsorted list. Its procedure of doing this contains similarites to the quicksort algorithm, they are both developed by Tony Hoare.
In an array, it's rather trivial to find the maximum or the minimum. But things get hard if we are trying to find the median or the 12th smallest element out of 100. We can of course sort, but that would take linearithmic time. Quickselect performs in linear time on avarage, it partially sorts the array as well.
To find the kth smallest element, we choose some random pivot. We then transfer every element smaller than this pivot the the start of the array. If the transfer index, new pivot, is greater than k, that means that the kth element is among these. If the new pivot is larger, that means that the kth element is among the elements that were not transferred. So, we partition the array each time and eventually find the kth element.
It could also be implemented as an iterative algorithm, where we can also move right elements to the other side of the pivot.
The quick sort algoirtmh can be further improved using the Median of medians algorithm.
Problem: https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/
Solution:
As we are incrementing and decrementing elements one-by-one, the least amount of moves should be acquired through converging the largest and the smallest values to some middle value, namely the median. We can find the median of the array trivially by sorting it and checking its middle element. We can also utilize the quicksort algorithm explained below. Beyond just finding the median, one can also consider how much the largest and the smallest value in the need to be decremented or incremented to have them converge to some value. If the largest is b and the smallest is a, moving both of them to c would cost
b-c + c-a = b-a. We can sort the array and use this for every larger and smaller element as we converge into the middle.Quickselect
Quickselect is an algorithm used for finding the kth smallest element in an unsorted list. Its procedure of doing this contains similarites to the quicksort algorithm, they are both developed by Tony Hoare. In an array, it's rather trivial to find the maximum or the minimum. But things get hard if we are trying to find the median or the 12th smallest element out of 100. We can of course sort, but that would take linearithmic time. Quickselect performs in linear time on avarage, it partially sorts the array as well. To find the kth smallest element, we choose some random pivot. We then transfer every element smaller than this pivot the the start of the array. If the transfer index, new pivot, is greater than k, that means that the kth element is among these. If the new pivot is larger, that means that the kth element is among the elements that were not transferred. So, we partition the array each time and eventually find the kth element.
It could also be implemented as an iterative algorithm, where we can also move right elements to the other side of the pivot.
The quick sort algoirtmh can be further improved using the
Median of mediansalgorithm.