453. Minimum Moves to Equal Array Elements

Problem Description

The problem asks us to determine the minimum number of moves required to make all elements of an array equal. A move is defined as incrementing n - 1 elements of the array by 1, where n is the size of the array. This means that in each move, all elements except one will be increased by one unit.

Intuition

The key insight for solving this problem is to realize that incrementing n - 1 elements by 1 is the same as decrementing 1 element by 1 with respect to the goal of making all elements equal. Imagine you have a set of numbers, and you want to make them all the same. Instead of adding 1 to all other numbers except the maximum (which is effectively trying to bring all numbers up to the level of the highest number), you can think of it as reducing the max number by 1 to reach the lower numbers. Therefore, the most efficient way to make all elements equal is to decrement the maximum number in the array until all the elements are equal to the minimum number in the array.

The number of moves it takes to make the maximum number equal to the minimum number is the difference between these two numbers. To generalize this, the number of moves required to make all numbers in the array equal to the minimum number is the sum of the differences between every number in the array and the minimum number.

The solution provided follows this philosophy. It calculates the sum of all numbers in the array and subtracts the minimum number times the length of the array. The subtraction term (min(nums) * len(nums)) represents the total value of the array if all elements were the minimum number. By subtracting this from the actual sum of the array (sum(nums)), we get the total number of increments needed to make all elements equal.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological SortUniform Cost SearchMonotonic StackMemoization

I don’t know

Solution Approach

The solution's approach involves understanding how simple math can translate into an algorithmic optimization. Instead of simulating each move — which would be inefficient for large arrays — we use a single pass calculation.

Algorithmically, we use a single loop provided by the sum function to calculate the sum of all elements in nums. We also use the built-in min function which also iterates over the array to find the minimum value. There are no complex data structures involved: the input is an integer array, and the output is a single integer value representing the minimum moves.

Here's a breakdown of the steps involved in the implementation of the solution:

Calculate the sum of all numbers in the array with sum(nums) which iterates over nums once.
Find the minimum number in the array with min(nums) which also iterates over nums once.
Multiply the minimum element by the number of elements in the array with min(nums) * len(nums). This gives the sum of elements if all of them were the minimum value.
Subtract the sum of all elements as if they were the minimum value from the actual sum of the array elements to get the total number of increments needed.
The result of the subtraction sum(nums) - min(nums) * len(nums) is the answer to the problem, which is returned by the solution function.

This approach uses the property of linearity in arithmetic operations — specifically, the distributive property allows us to condense the whole operation into a single expression. The formula is derived from the insight that bringing the maximum element down to the minimum is equivalent to making all elements equal by the least number of increments.

The algorithm runs in O(n) time complexity because it involves a full pass through the array twice (one for sum and one for min) and O(1) space complexity, as no additional space is used proportional to the input size (constant extra space is used for storing the sum, minimum, and result).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have the following array of numbers: nums = [1, 2, 3, 4].

To find the minimum number of moves to make all elements equal by incrementing n - 1 elements (where n is the length of the array), we proceed with the following steps:

Calculate the Sum: First, we find the sum of all the numbers in the array. For our example, sum(nums) = 1 + 2 + 3 + 4 = 10.
Find the Minimum Element: Next, we determine the minimum element in the array. In this case, min(nums) = 1.
Multiply Minimum Element by Array Length: After that, we multiply the minimum number by the number of elements (n) in the array: min(nums) * len(nums) = 1 * 4 = 4.
Find the Required Moves: Finally, the total number of moves required is obtained by subtracting the product found in the previous step from the total sum: sum(nums) - min(nums) * len(nums) = 10 - 4 = 6.

Thus, the minimum number of moves required to make all elements equal in this example is 6.

Repeat these steps with any array, and you'll get the minimum number of moves needed without incrementing each time, but rather by realizing incrementing n - 1 is the inverse of decrementing 1. This simple calculation saves time and computational resources.

Solution Implementation

1class Solution:
2    def minMoves(self, nums) -> int:
3        # Calculate the sum of all numbers in the list
4        total_sum = sum(nums)
5        # Find the minimum value in the list
6        min_value = min(nums)
7        # Calculate the number of moves required to equalize the values
8        # by subtracting the product of the minimum value and list length from the total sum
9        moves = total_sum - min_value * len(nums)
10      
11        return moves
12

1import java.util.Arrays; // Import Arrays utility to use its methods
2
3class Solution {
4    public int minMoves(int[] nums) {
5        // Calculate the sum of all elements in the array
6        int sum = Arrays.stream(nums).sum();
7      
8        // Find the minimum element in the array
9        int min = Arrays.stream(nums).min().getAsInt();
10      
11        // The minimum number of moves is the sum of elements minus
12        // the minimum element multiplied by the number of elements in the array.
13        // This is because in each move you can increment n-1 elements (all but the max),
14        // which is mathematically equivalent to decrementing the maximum element.
15        // The target is making all elements equal to the minimum, hence the formula.
16        int minMoves = sum - min * nums.length;
17      
18        return minMoves;
19    }
20}
21

1#include <vector>
2#include <algorithm> // Include algorithm for using the min function
3
4class Solution {
5public:
6    // Calculate the minimum number of moves to make all array elements equal
7    // by incrementing n-1 elements by 1 each move
8    int minMoves(vector<int>& nums) {
9        int sum = 0; // Initialize sum of all elements in the array
10        int minVal = INT_MAX; // Initialize the smallest value found in the array to the maximum possible integer value
11
12        // Loop through all elements in the nums array
13        for (int num : nums) {
14            sum += num; // Add the current element's value to the sum
15            minVal = min(minVal, num); // Update minVal if the current element's value is smaller
16        }
17
18        // The minimum number of moves is the total sum of array elements
19        // minus the product of the array's size and the smallest element in the array
20        return sum - minVal * nums.size();
21    }
22};
23

1/**
2 * Calculates the minimum number of moves required to make all array elements equal,
3 * where a move is defined as incrementing n - 1 elements by 1.
4 * 
5 * @param {number[]} nums - an array of integers.
6 * @return {number} - the minimum number of moves.
7 */
8function minMoves(nums: number[]): number {
9    // Initialize the minimum element to a large number.
10    let minValue = Number.MAX_SAFE_INTEGER;
11    // Initialize sum to store the total sum of the array elements.
12    let sum = 0;
13
14    // Iterate through the array to find the total sum and the minimum value.
15    for (const num of nums) {
16        sum += num;
17        minValue = Math.min(minValue, num);
18    }
19
20    // The minimum number of moves to equalize all elements is
21    // the total sum minus the product of the minimum value and the array's length.
22    return sum - minValue * nums.length;
23}
24

Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n) where n is the length of the list nums. The reason for this is that the function performs two operations that depend linearly on the size of the input list:

The sum(nums) operation iterates through the list to calculate the sum of all its elements.
The min(nums) operation iterates through the list to find the minimum element.

Both these operations take O(n) time as each element of nums must be visited once.

Therefore, considering these two primary operations, the total time complexity remains O(n).

Space Complexity

The space complexity of the code is O(1). It uses a constant amount of extra space regardless of the size of the input list nums. The additional space is used for storing the sum of the elements, the minimum element, and the result of the expression sum(nums) - min(nums) * len(nums). None of these require space that scales with the input size, hence the space complexity is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

453. Minimum Moves to Equal Array Elements

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings