453. Minimum Moves to Equal Array Elements - Detailed Explanation

Problem Statement

Given an array of integers, you can perform a move where you increment every element except one by 1. The goal is to determine the minimum number of moves required to make all the elements of the array equal.

For example, if the array is [1, 2, 3], you want to perform the minimum moves such that all elements become equal.

Example Inputs, Outputs, and Explanations

Example 1

• Input: [1, 2, 3]
• Output: 3
• Explanation:
  The optimal strategy is to decrement the larger numbers indirectly. Instead of thinking of it as incrementing all but one, you can reverse the perspective and think of it as decrementing one element at a time.
  The minimum element is 1. To make every element equal to 1, you need to subtract:
  • From 2: (2 - 1) = 1 move
  • From 3: (3 - 1) = 2 moves
    Total moves = 1 + 2 = 3.

Example 2

• Input: [5, 6, 8, 8, 5]
• Output: 7
• Explanation:
  The minimum element in the array is 5. The moves required for each element are:
  • For 5: (5 - 5) = 0
  • For 6: (6 - 5) = 1
  • For 8: (8 - 5) = 3 (and there are two 8's, so 3+3)
  • For the other 5: (5 - 5) = 0
    Total moves = 0 + 1 + 3 + 3 + 0 = 7.

Hints

1. Reverse the Operation:
   Notice that incrementing all elements except one is equivalent to decrementing that one element by 1 relative to the others. This change in perspective makes the problem easier to solve.

2. Find the Minimum Element:
   The optimal strategy is to equalize all elements to the minimum value in the array. Every move is effectively a decrement on one element. The number of moves required is the sum of differences between each element and the minimum element.

Approach: Summing the Differences

Explanation

1. Identify the Minimum:
   Find the minimum element in the array. This is the target value that all other elements need to be reduced to.

2. Calculate the Moves:
   For each element in the array, compute the difference between the element and the minimum element. The sum of all these differences gives the minimum number of moves required.

3. Why It Works:
   Each move, by incrementing all but one element, can be seen as reducing the gap between the largest element and the smallest element by 1. Repeating this process until all elements are equal is the same as decrementing each element to the minimum value.

Step-by-Step Walkthrough

Consider the array [1, 2, 3]:

• Find the minimum element: min = 1.
• Calculate the differences:
  • For 1: 1 - 1 = 0 moves.
  • For 2: 2 - 1 = 1 move.
  • For 3: 3 - 1 = 2 moves.
• Total moves required = 0 + 1 + 2 = 3.

Complexity Analysis

• Time Complexity: O(n), where n is the number of elements in the array. This is due to a single pass needed to find the minimum and another pass to compute the differences.

• Space Complexity: O(1) since only a few extra variables are used.

Python Code