Minimum Moves to Equal Array Elements

MEDIUM

Description

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

Checkout 3 different approaches to solve Minimum Moves to Equal Array Elements. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation

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.

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.

public class Solution {
    public int minMoves(int[] nums) {
        int moves = 0;
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        while (true) {
            int min = nums[0];
            int max = nums[0];
            int max_idx = 0;

            for (int i = 1; i < n; i++) {
                if (nums[i] < min) {
                    min = nums[i];
                }
                if (nums[i] > max) {
                    max = nums[i];
                    max_idx = i;
                }
            }

            if (min == max) {
                break;
            }

            for (int i = 0; i < n; i++) {
                if (i != max_idx) {
                    nums[i]++;
                }
            }
            moves++;
        }
        return moves;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as we modify the array in-place and use only a constant amount of extra space for variables.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Moves to Equal Array Elements. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Minimum Moves to Equal Array Elements

Patterns:

Math

Data Structures:

Array

Companies:

Indeed |Coursera |