Minimum Moves to Equal Array Elements

Med

#0440Time: O(m * n), where `n` is the length of the array and `m` is the total number of moves. Each move requires O(n) time to find the maximum element and update the others. Since `m` can be very large (up to the order of 10^9), this approach is not feasible.Space: O(1), as we modify the array in-place and use only a constant amount of extra space for variables.2 companies

Patterns

Math

Data structures

Array

Companies

Indeed Coursera

Prompt

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 n - 1 elements of the array by 1.

Example 1:

Input: nums = [1,2,3]
Output: 3
Explanation: Only three moves are needed (remember each move increments two elements):
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Example 2:

Input: nums = [1,1,1]
Output: 0

Constraints:

n == nums.length
1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
The answer is guaranteed to fit in a 32-bit integer.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We repeatedly find the largest element and increment all other n-1 elements by 1. We keep a count of these operations, called 'moves'. The simulation stops when all elements in the array become equal, and we return the total count of moves.

Algorithm

Initialize a moves counter to 0.
Start an infinite loop.
Inside the loop, check if all elements in the array are equal. A simple way is to find the minimum and maximum elements; if they are the same, all elements are equal.
If they are equal, break the loop and return moves.
If not, find the index of the maximum element.
Iterate through the array and increment every element by 1, except for the maximum element.
Increment the moves counter.

Walkthrough

The brute-force method involves a loop that continues as long as the array's elements are not all identical. In each iteration of this loop, we perform one 'move'. A move consists of finding the largest value in the array and then incrementing all other n-1 elements. A counter tracks the number of moves. The process is guaranteed to terminate because the difference between the maximum and minimum elements decreases or stays the same in each step, but the values themselves increase, eventually converging. However, the number of moves can be very large, making this simulation too slow for the given constraints.

1public class Solution {2    public int minMoves(int[] nums) {3        int moves = 0;4        int n = nums.length;5        if (n <= 1) {6            return 0;7        }8 9        while (true) {10            int min = nums[0];11            int max = nums[0];12            int max_idx = 0;13 14            for (int i = 1; i < n; i++) {15                if (nums[i] < min) {16                    min = nums[i];17                }18                if (nums[i] > max) {19                    max = nums[i];20                    max_idx = i;21                }22            }23 24            if (min == max) {25                break;26            }27 28            for (int i = 0; i < n; i++) {29                if (i != max_idx) {30                    nums[i]++;31                }32            }33            moves++;34        }35        return moves;36    }37}

Complexity

Time

O(m * n), where `n` is the length of the array and `m` is the total number of moves. Each move requires O(n) time to find the maximum element and update the others. Since `m` can be very large (up to the order of 10^9), this approach is not feasible.

Space

O(1), as we modify the array in-place and use only a constant amount of extra space for variables.

Trade-offs

Pros

It is straightforward to understand as it directly models the problem statement.

Cons

Extremely inefficient due to its high time complexity.
It will result in a 'Time Limit Exceeded' error for most competitive programming platforms on medium to large inputs.

A crucial observation is that incrementing n-1 elements by 1 has the same effect on the relative differences between elements as decrementing a single element by 1. To make all elements equal, we must bring them all to a common value. To minimize the number of moves (or decrements), the target value must be the minimum element of the original array. Therefore, the problem reduces to calculating the sum of differences between each element and the minimum element. This approach first sorts the array to easily identify the minimum element.

Algorithm

Sort the input array nums in ascending order.
The first element, nums[0], is now the minimum element in the array.
Initialize a variable moves to 0.
Iterate through the array from the second element (i = 1) to the end.
For each element nums[i], calculate the difference nums[i] - nums[0] and add it to moves.
After the loop, moves will hold the total number of moves required. Return moves.

Walkthrough

By rephrasing the problem, we can find a more efficient solution. Instead of incrementing n-1 elements, we can think of it as decrementing one element. The goal is to make all elements equal. The most efficient way to do this by decrementing is to make all elements equal to the initial minimum value. The total number of moves is the sum of nums[i] - min_val for all elements nums[i].

This approach first sorts the array, which places the minimum element at the first index (nums[0]). Then, it iterates through the rest of the array, summing up the differences between each element and this minimum value.

1import java.util.Arrays;2 3public class Solution {4    public int minMoves(int[] nums) {5        Arrays.sort(nums);6        int moves = 0;7        for (int i = 1; i < nums.length; i++) {8            moves += nums[i] - nums[0];9        }10        return moves;11    }12}

Complexity

Time

O(n log n), dominated by the sorting step. The subsequent loop to sum the differences takes O(n) time.

Space

O(log n) to O(n), depending on the sorting algorithm's implementation. For instance, Java's `Arrays.sort` for primitives uses a variant of Quicksort, which has an average space complexity of O(log n) for the recursion stack.

Trade-offs

Pros

Significantly more efficient than the brute-force simulation.
Based on a correct mathematical insight that simplifies the problem.

Cons

The time complexity is dominated by sorting, which is not the most optimal way to find the minimum element.

This is the most optimal approach. It uses the same mathematical insight as the sorting approach: the total number of moves is sum(nums) - n * min_val. However, it recognizes that sorting is an unnecessary step. Both the sum of the array and its minimum element can be found in a single pass, leading to a linear time solution.

Algorithm

Initialize min_val to Integer.MAX_VALUE and sum to 0 (using a long type for sum to prevent overflow).
Iterate through the array nums once.
In each iteration, add the current element to sum.
Also, update min_val if the current element is smaller than the current min_val.
After the loop, you will have the sum of all elements and the minimum element.
The result is sum - (n * min_val), where n is the length of the array. Cast the final result back to int as the answer is guaranteed to fit.

Walkthrough

This approach is based on the formula moves = sum(nums) - n * min_val. To calculate this, we need two values: the sum of all elements and the minimum element in the array. Both of these can be computed efficiently by iterating through the array just once. We maintain a running sum and simultaneously track the minimum value seen so far. After a single pass, we have both values and can compute the result directly. This avoids the O(n log n) cost of sorting.

1public class Solution {2    public int minMoves(int[] nums) {3        if (nums.length == 0) {4            return 0;5        }6        7        long sum = 0;8        int min_val = Integer.MAX_VALUE;9        10        for (int num : nums) {11            sum += num;12            min_val = Math.min(min_val, num);13        }14        15        return (int)(sum - (long)nums.length * min_val);16    }17}

Using long for the sum and during the calculation is a safe practice to prevent intermediate overflow, especially since element values can be large, even though the final answer is guaranteed to fit in a 32-bit integer.

Complexity

Time

O(n), because we iterate through the array only once to find the sum and the minimum element.

Space

O(1), as it only requires a few variables to store the sum and the minimum value, independent of the input size.

Trade-offs

Pros

Optimal time complexity of O(n).
Optimal space complexity of O(1).
Simple to implement once the mathematical formula is known.

Cons

The underlying mathematical trick might not be immediately obvious to everyone.

Solutions

Solution

1class Solution { public int minMoves ( int [] nums ) { return Arrays . stream ( nums ). sum () - Arrays . stream ( nums ). min (). getAsInt () * nums . length ; } }

1class Solution { public: int minMoves ( vector < int >& nums ) { int s = 0 ; int mi = 1 << 30 ; for ( int x : nums ) { s += x ; mi = min ( mi , x ); } return s - mi * nums . size (); } };

1class Solution : def minMoves ( self , nums : List [ int ]) -> int : return sum ( nums ) - min ( nums ) * len ( nums )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution { public int minMoves ( int [] nums ) { return Arrays . stream ( nums ). sum () - Arrays . stream ( nums ). min (). getAsInt () * nums . length ; } }

1class Solution { public: int minMoves ( vector < int >& nums ) { int s = 0 ; int mi = 1 << 30 ; for ( int x : nums ) { s += x ; mi = min ( mi , x ); } return s - mi * nums . size (); } };

1class Solution : def minMoves ( self , nums : List [ int ]) -> int : return sum ( nums ) - min ( nums ) * len ( nums )

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.