372. Minimum Moves to Equal Array Elements II
You are given an integer array nums.
In one move you may pick any single element and change it by exactly 1 — either up or down. Moves on different elements are independent, and you may spend as many moves on one element as you like.
Return the minimum total number of moves required to make every element of the array equal. The answer can exceed the 32-bit range.
Example 1:
Input: nums = [1, 2, 3]
Output: 2
Explanation: Meet at 2: raising 1 costs one move and lowering 3 costs one move, for a total of 2. No meeting point does better.
Example 2:
Input: nums = [1, 10, 2, 9]
Output: 16
Explanation: Any value from 2 through 9 works equally well as the meeting point. Meeting at 2 costs 1 + 8 + 0 + 7 = 16.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
- The answer fits in a 64-bit signed integer.
Hints:
The cost of gathering everyone at a value t is Σ |nums[i] − t|. The mean minimizes squared distance, but absolute distance has a different champion.
Slide t one step to the right: every element below t pays one more move, every element above pays one less. The total keeps improving until the number of elements on each side balances — that balance point is the median.
Sort and take the middle element (either middle works when n is even), then sum the absolute gaps. Quickselect can find the median in O(n) average if you want to skip the full sort.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3]
Expected output: 2