LeetCode 3736 - Minimum Moves to Equal Array Elements III

The problem asks us to determine the minimum number of moves required to make every element in an integer array equal. A move consists of selecting one element and increasing it by exactly 1. We are not allowed to decrease values, and we can only increment elements.

leetcodeeasyarraymath

LeetCode Problem 3736

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to determine the minimum number of moves required to make every element in an integer array equal. A move consists of selecting one element and increasing it by exactly 1. We are not allowed to decrease values, and we can only increment elements.

In other words, we need to choose a target value such that every number in the array can be increased to that value using the fewest total operations. Since decreasing is not allowed, the target value must be at least as large as the largest element already present.

The input is an integer array nums, where each value represents an element that can be incremented independently. The output is a single integer representing the minimum total number of increment operations needed so that all values become identical.

The constraints are small:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

These limits tell us that performance is not a major concern. Even less efficient approaches would work comfortably. However, the problem contains an important mathematical observation that allows us to solve it in a very clean and optimal way.

An important detail is that we can only increase elements. This restriction changes the strategy completely. If decreasing were allowed, we might choose something like the median, but here the only valid final value is the maximum element in the array. Choosing anything smaller is impossible because larger numbers cannot be reduced. Choosing anything larger would only add unnecessary operations.

Some important edge cases include arrays with only one element, arrays where all values are already equal, and arrays with a large gap between minimum and maximum values. The problem guarantees that the array is non-empty, so we never need to handle an invalid or empty input.

Approaches

Brute Force Approach

A brute force solution would try every possible target value and calculate how many moves are needed to make all elements equal to that target.

Since we can only increase numbers, the target must be at least the maximum element. We could try every target from max(nums) up to some upper bound, compute the cost for each candidate, and return the minimum.

For each candidate target, we would iterate through the array and sum:

$$target - nums[i]$$

for every element.

This works because it explicitly evaluates every possible valid ending state and chooses the smallest cost. However, it is unnecessary because targets larger than the maximum only increase the number of required moves. The minimum will always occur at the maximum value itself.

Although this approach is technically correct, it performs redundant work.

Optimal Approach

The key observation is that since we are only allowed to increase elements, the final equal value must be the maximum element already in the array.

Suppose the maximum element is M.

  • Any value smaller than M is impossible because M cannot be decreased.
  • Any value larger than M is wasteful because every element, including M, would need extra increments.

Therefore, the optimal target is exactly:

$$\text{target} = \max(nums)$$

Once we know the target, the answer becomes simple. For every element:

$$\text{moves} += target - num$$

The total sum of these differences gives the minimum required moves.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × k) O(1) Tries multiple target values, redundant work
Optimal O(n) O(1) Uses the maximum element as the only valid target

Here, n is the length of the array and k represents the number of candidate target values checked in the brute force method.

Algorithm Walkthrough

  1. Find the maximum value in the array.

This value becomes the target because all elements can be increased to it, and any larger target would require unnecessary moves. 2. Initialize a variable total_moves = 0.

This variable will accumulate the total number of increments required. 3. Iterate through every number in the array.

For each value num, compute:

$$target - num$$

This tells us exactly how many increments are needed to raise num to the target. 4. Add the required increments to total_moves.

Repeat this for all elements. 5. Return total_moves.

After processing the entire array, the accumulated value represents the minimum number of moves needed.

Why it works

The correctness comes from the fact that only increment operations are allowed. Since we cannot reduce any value, the final equal number cannot be smaller than the maximum element. At the same time, choosing a value larger than the maximum introduces unnecessary increments for every element. Therefore, the maximum element is the unique optimal target, and summing the differences to this target gives the minimum possible move count.

Python Solution

from typing import List

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        target = max(nums)
        total_moves = 0

        for num in nums:
            total_moves += target - num

        return total_moves

The implementation begins by finding the largest element in the array using max(nums). This value becomes the target that every element must reach.

Next, we initialize total_moves to track the total number of increment operations.

We then iterate through every number in the array. For each element, we compute how many increments are required to reach the target by subtracting the current value from the maximum value. This difference is added to the running total.

Finally, we return the accumulated number of moves.

The implementation directly mirrors the mathematical observation from the algorithm. Since each element independently needs target - num increments, summing these values naturally produces the minimum total.

Go Solution

func minMoves(nums []int) int {
    target := nums[0]

    for _, num := range nums {
        if num > target {
            target = num
        }
    }

    totalMoves := 0

    for _, num := range nums {
        totalMoves += target - num
    }

    return totalMoves
}

The Go implementation follows the same logic as the Python solution. Since Go does not have a built-in max function for slices, we manually scan the array to find the maximum value.

After determining the target, we perform a second pass to calculate the total number of increments needed.

Because the constraints are very small and values are bounded by 100, integer overflow is not a concern. The input is guaranteed to contain at least one element, so accessing nums[0] is safe.

Worked Examples

Example 1

Input:

nums = [2, 1, 3]

First, find the maximum element:

target = 3

Now compute the required moves for each element.

Index Value Target Moves Needed Running Total
0 2 3 1 1
1 1 3 2 3
2 3 3 0 3

Final answer:

3

Example 2

Input:

nums = [4, 4, 5]

First, find the maximum element:

target = 5

Now calculate the increments needed.

Index Value Target Moves Needed Running Total
0 4 5 1 1
1 4 5 1 2
2 5 5 0 2

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass to find the maximum and one pass to compute moves
Space O(1) Only a few variables are used

The algorithm runs in linear time because each element is processed a constant number of times. We first determine the maximum value, then iterate again to compute the required increments. No additional data structures proportional to input size are used, so the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.minMoves([2, 1, 3]) == 3  # Example 1
assert solution.minMoves([4, 4, 5]) == 2  # Example 2

assert solution.minMoves([7]) == 0  # Single element array
assert solution.minMoves([5, 5, 5]) == 0  # Already equal
assert solution.minMoves([1, 100]) == 99  # Large difference between values
assert solution.minMoves([1, 2, 3, 4]) == 6  # Increasing sequence
assert solution.minMoves([10, 1, 1]) == 18  # One large maximum
assert solution.minMoves([100, 100, 100, 100]) == 0  # All max values
assert solution.minMoves([1, 1, 100]) == 198  # Extreme gap case
assert solution.minMoves([3, 2, 2, 3]) == 2  # Mixed duplicates
Test Why
[2,1,3] Validates the first provided example
[4,4,5] Validates the second provided example
[7] Tests smallest valid input
[5,5,5] Ensures zero moves when already equal
[1,100] Tests large value gap
[1,2,3,4] Verifies accumulation across multiple elements
[10,1,1] Ensures correct handling of one dominant maximum
[100,100,100,100] Confirms no unnecessary moves
[1,1,100] Tests extreme difference scenario
[3,2,2,3] Validates handling of duplicates

Edge Cases

Single Element Array

An array with only one element, such as [7], requires zero moves because all elements are already equal. A naive implementation might unnecessarily process or modify the value, but this solution naturally returns 0 because the maximum equals the element itself.

All Elements Already Equal

For an input like [5, 5, 5], every element already matches the maximum value. Each subtraction becomes:

5 - 5 = 0

The accumulated total remains zero, ensuring no unnecessary operations are counted.

Large Difference Between Minimum and Maximum

Cases such as [1, 1, 100] can expose arithmetic mistakes in implementations that incorrectly choose the target value. If the target were chosen larger than the maximum, the answer would be inflated. This implementation correctly uses 100 as the target and computes:

(100 - 1) + (100 - 1) + (100 - 100)
= 99 + 99 + 0
= 198

which is the true minimum.