Minimum Moves to Equal Array Elements II solution and explanation
TCS
Google
9 more videos on this problem
Minimum Moves to Equal Array Elements II | Live Coding with Explanation | Leetcode - 462Algorithms Made Easy · 9:30 · 18K views
Leetcode 462. Minimum Moves to Equal Array Elements IICode with Alisha · 17:20 · 17K views
Leetcode - Minimum Moves to Equal Array Elements II (Python)Timothy H Chang · 5:04 · 2K views
Minimum Moves to Equal Array Elements II | Leetcode 462 | Live coding sessionCoding Decoded · 4:45 · 2K views
Minimum Moves to Equal Array Elements II | Maths | Median | 462 LeetCode | Day 19CodeWithSunny · 11:33 · 838 views
462. Minimum Moves to Equal Array Elements IITech Adora by Nivedita · 4:11 · 822 views
Daily Leetcode #821: Jun 30, 2022 - 462. Minimum Moves to Equal Array Elements IIProgramming Live with Larry · 11:12 · 652 views
Leetcode 462 Minimum Moves to Equal Array Elements II | 👉🏼 Coding Decoded SDE SheetCoding Decoded · 3:22 · 578 views
Minimum Moves to Equal Array Elements II | LeetCode 462 | Coders CampCoders Camp · 8:30 · 561 views
Leetcode 462: Minimum Moves to Equal Array Elements IIBlake Wright · 6:14 · 414 views
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.
Test cases are designed so that the answer will fit in a 32-bit integer.
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.length1 <= nums.length <= 105-109 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an integer array where one move allows incrementing or decrementing a single element by 1. The goal is to make all elements equal using the minimum number of moves. The challenge is choosing the optimal target value that minimizes the total distance from every element.
Approach 1: Median as Optimal Point (Sorting + Math) (Time: O(n log n), Space: O(1) or O(n) depending on sorting)
The key insight comes from math: the sum of absolute differences |a[i] − x| is minimized when x is the median of the array. Start by sorting the array using a sorting algorithm. Once sorted, pick the middle element as the median. Then iterate through the array and accumulate abs(num - median) for each value. This works because moving values toward the median minimizes total movement compared with choosing the mean or any other value.
This approach is straightforward and reliable in interviews. Sorting costs O(n log n) time, while the final pass to compute moves takes O(n). Extra space is constant if the language sorts in place.
Approach 2: Two Pointers Technique (Sorted Array Pair Balancing) (Time: O(n log n), Space: O(1))
After sorting the array, you can compute the same result without explicitly calculating the median. Use two pointers: one at the start and one at the end of the array. Each pair contributes nums[right] - nums[left] moves because both numbers will eventually meet at the median. Move the pointers inward until they meet. The accumulated difference across all pairs equals the minimum moves required.
This works because every pair of elements symmetrically approaches the median during optimal adjustments. Sorting groups values so the smallest and largest converge step by step. The two‑pointer scan runs in O(n) time after sorting and uses constant extra space.
The problem is fundamentally about minimizing absolute distance in an array. Both methods rely on the same mathematical property of medians. The difference lies in implementation style: explicitly computing the median versus aggregating pair differences.
Recommended for interviews: The median insight is what interviewers want to see. Explaining why the median minimizes absolute distance demonstrates algorithmic reasoning. Implementing the two‑pointer version afterward shows you understand how the sorted structure leads to the same result efficiently.
Approach 1: Median as Optimal Point
To minimize the number of moves, the optimal strategy is to move all numbers to the median of the array. The median minimizes the sum of absolute deviations (L1 norm), which provides the least number of moves required to make all elements equal. By sorting the array and picking the middle element (or the average of two middle elements for an even-sized array), we can find the median efficiently.
def min_moves2(nums):
nums.sort()
median = nums[len(nums) // 2]
moves = sum(abs(num - median) for num in nums)
return moves
# Test case
test = [1, 2, 3]
print(min_moves2(test))import java.util.Arrays;
class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int median = nums[nums.length / 2];
int moves = 0;
for (int num : nums) {
moves += Math.abs(num - median);
}
return moves;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3};
System.out.println(sol.minMoves2(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minMoves2(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int median = nums[nums.size() / 2];
int moves = 0;
for (int num : nums) {
moves += std::abs(num - median);
}
return moves;
}
int main() {
std::vector<int> nums = {1, 2, 3};
std::cout << minMoves2(nums) << std::endl;
return 0;
}function minMoves2(nums) {
nums.sort((a, b) => a - b);
const median = nums[Math.floor(nums.length / 2)];
return nums.reduce((acc, num) => acc + Math.abs(num - median), 0);
}
console.log(minMoves2([1, 2, 3]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int minMoves2(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
int median = nums[numsSize / 2];
int moves = 0;
for (int i = 0; i < numsSize; i++) {
moves += abs(nums[i] - median);
}
return moves;
}
int main() {
int nums[] = {1, 2, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minMoves2(nums, size));
return 0;
}using System;
class Solution {
public int MinMoves2(int[] nums) {
Array.Sort(nums);
int median = nums[nums.Length / 2];
int moves = 0;
foreach (int num in nums) {
moves += Math.Abs(num - median);
}
return moves;
}
static void Main() {
var sol = new Solution();
int[] nums = {1, 2, 3};
Console.WriteLine(sol.MinMoves2(nums));
}
}The Python solution leverages Python's sorted function and a generator expression to calculate moves efficiently.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) excluding generator memory use.
Approach 2: Two Pointers Technique
This approach uses a two-pointer technique on a sorted version of the array to calculate the minimum moves. We initialize two pointers, one at the beginning and the other at the end of the sorted array. By incrementing the left pointer and decrementing the right pointer, we accumulate the number of moves required to make each element pair equal.
def min_moves2(nums):
nums.sort()
moves = 0
left, right = 0, len(nums) - 1
while left < right:
moves += nums[right] - nums[left]
left += 1
right -= 1
return moves
# Test case
test = [1, 10, 2, 9]
print(min_moves2(test))import java.util.Arrays;
class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int moves = 0;
int left = 0, right = nums.length - 1;
while (left < right) {
moves += nums[right] - nums[left];
left++;
right--;
}
return moves;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 10, 2, 9};
System.out.println(sol.minMoves2(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minMoves2(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int moves = 0;
int i = 0, j = nums.size() - 1;
while (i < j) {
moves += nums[j] - nums[i];
i++; j--;
}
return moves;
}
int main() {
std::vector<int> nums = {1, 10, 2, 9};
std::cout << minMoves2(nums) << std::endl;
return 0;
}function minMoves2(nums) {
nums.sort((a, b) => a - b);
let moves = 0;
let left = 0, right = nums.length - 1;
while (left < right) {
moves += nums[right] - nums[left];
left++;
right--;
}
return moves;
}
console.log(minMoves2([1, 10, 2, 9]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int minMoves2(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
int moves = 0;
int i = 0;
int j = numsSize - 1;
while (i < j) {
moves += nums[j] - nums[i];
i++; j--;
}
return moves;
}
int main() {
int nums[] = {1, 10, 2, 9};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minMoves2(nums, size));
return 0;
}using System;
class Solution {
public int MinMoves2(int[] nums) {
Array.Sort(nums);
int moves = 0;
int left = 0, right = nums.Length - 1;
while (left < right) {
moves += nums[right] - nums[left];
left++;
right--;
}
return moves;
}
static void Main() {
var sol = new Solution();
int[] nums = {1, 10, 2, 9};
Console.WriteLine(sol.MinMoves2(nums));
}
}In Python, the two-pointer method is implemented similarly, handling boundary conditions and computes moves efficiently.
Time Complexity: O(n log n) due to sort.
Space Complexity: O(1).
Approach 3: Sorting + Median
This problem can be abstracted to finding a point on a number line such that the sum of distances from n points to this point is minimized. The answer is the median of the n points.
The median has the property that the sum of distances from all numbers to the median is minimized.
Proof:
First, given a sorted sequence a_1, a_2, cdots, a_n, we assume x is the point that minimizes the sum of distances from a_1 to a_n. Clearly, x must lie between a_1 and a_n. Since the distances from a_1 and a_n to x are equal and both equal to a_n - a_1, we can ignore a_1 and a_n and only consider a_2, a_3, cdots, a_{n-1}. This reduces the problem to finding a point within a_2, a_3, cdots, a_{n-1} that minimizes the sum of distances. By iterating this process, we conclude that the median of a sequence minimizes the sum of distances to the other numbers.
In this problem, we can first sort the array, then find the median, and finally calculate the sum of distances from all numbers to the median.
The time complexity is O(n log n), and the space complexity is O(log n).
Similar problems:
function minMoves2(nums: number[]): number {
nums.sort((a, b) => a - b);
const k = nums[nums.length >> 1];
return nums.reduce((r, v) => r + Math.abs(v - k), 0);
}func minMoves2(nums []int) int {
sort.Ints(nums)
k := nums[len(nums)>>1]
ans := 0
for _, v := range nums {
ans += abs(v - k)
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn min_moves2(mut nums: Vec<i32>) -> i32 {
nums.sort();
let k = nums[nums.len() / 2];
let mut ans = 0;
for num in nums.iter() {
ans += (num - k).abs();
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Median as Optimal Point | Time Complexity: O(n log n) due to sorting. |
| Two Pointers Technique | Time Complexity: O(n log n) due to sort. |
| Sorting + Median | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Median as Optimal Point | O(n log n) | O(1) | General case; easiest implementation when you directly compute the median |
| Two Pointers on Sorted Array | O(n log n) | O(1) | When the array is already sorted or when you prefer pair balancing logic |
Frequently asked questions
Is Minimum Moves to Equal Array Elements II easy or hard?
Minimum Moves to Equal Array Elements II is classified as a Medium problem. The implementation is simple once you know the median property, but recognizing that the median minimizes total absolute distance is the main conceptual challenge.
Minimum Moves to Equal Array Elements II Python/Java solution
In Python or Java, the common implementation sorts the array, selects the middle element as the median, and sums absolute differences between each element and the median. This approach runs in O(n log n) time and requires only constant extra space beyond the array.
How to solve Minimum Moves to Equal Array Elements II in O(n)?
An O(n) solution is possible using a linear-time median selection algorithm such as Quickselect. First find the median without sorting the entire array, then compute the sum of absolute differences from that median in a single pass. The overall complexity becomes O(n) average time with O(1) extra space.
What is the best approach for Minimum Moves to Equal Array Elements II?
The optimal strategy is to move all elements toward the median of the array. The median minimizes the sum of absolute differences, which directly represents the number of moves required. After sorting the array, compute the median and sum abs(nums[i] - median) for every element. The time complexity is O(n log n) due to sorting.
Is Minimum Moves to Equal Array Elements II asked at Google/Amazon/Meta?
This problem appears in interview preparation sets used by companies like Amazon, Google, and Meta because it tests understanding of medians, absolute distance minimization, and array manipulation. Candidates are often expected to recognize the median property quickly.
What data structure is used in Minimum Moves to Equal Array Elements II?
The problem mainly uses arrays along with sorting or selection algorithms. Some implementations rely on two pointers after sorting the array, while others use Quickselect to find the median without fully sorting.
What is the time complexity of Minimum Moves to Equal Array Elements II?
The typical solution runs in O(n log n) time because the array must be sorted to determine the median. After sorting, calculating the total moves requires a single O(n) traversal. Space complexity is O(1) if sorting is done in place.