Jobs

Interviews

Discussions

Minimum Moves to Equal Array Elements

Medium

Asked by:

More companies

80 views

Topics:

Arrays

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.

Try coding it in LeetCode

Minimum Moves to Equal Array Elements

Medium

Asked by:

80 views

Topics:

Arrays

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the array? Can they be negative, zero, or are they strictly positive?
What are the constraints on the size of the array, `n`? For instance, what are the minimum and maximum possible number of elements?
The problem statement mentions a 'non-empty' array. Does this mean the array will always have at least one element? If so, what should be the output for a single-element array?
Are the integer values within a specific range, like the standard 32-bit signed integer range? This might be important to consider for potential overflow issues when summing elements.
Since we are incrementing `n-1` elements, could you confirm if this operation is equivalent to decrementing a single element by 1 in terms of the relative differences between elements?

Brute Force Solution

Approach

The brute force strategy is to simulate the process one move at a time. We repeatedly find the largest number and increase all the other numbers by one until every number in the collection is the same.

Here's how the algorithm would work step-by-step:

First, check if all the numbers in the collection are already the same. If they are, no moves are needed, and we're done.
If the numbers are not all equal, find the largest number in the group.
Now, take every other number in the collection (all of them except the largest one) and add one to each of them. This counts as a single move.
Keep track of how many moves you've made so far.
After making a move, go back and check again if all the numbers have become equal.
Continue this process of finding the largest, increasing the others, and counting the move, over and over, until all the numbers finally match.

Code Implementation

def min_moves_brute_force(numbers):
    number_of_moves = 0
    list_size = len(numbers)

    if list_size == 0:
        return 0

    while True:
        # This check is necessary to determine if the array elements are equal, which is our stop condition.
        all_elements_are_equal = all(element == numbers[0] for element in numbers)

        if all_elements_are_equal:
            break

        maximum_number = -float('inf')
        index_of_maximum = -1

        for current_index in range(list_size):
            if numbers[current_index] > maximum_number:
                maximum_number = numbers[current_index]
                index_of_maximum = current_index
        
        # Incrementing all elements except the max is the core logic of a single "move".
        for current_index in range(list_size):
            if current_index != index_of_maximum:
                numbers[current_index] += 1
        
        number_of_moves += 1

    return number_of_moves

Big(O) Analysis

Time Complexity

O(k * n) – The overall complexity is determined by the number of moves (k) required and the work done per move. In each move, we must iterate through the n elements to find the maximum and then iterate through them again to increment n-1 elements, which takes O(n) time. This process repeats k times, where k is the total number of moves, which is the difference between the final sum and the initial sum. Therefore, the total time complexity is the number of moves multiplied by the cost of each move, resulting in O(k * n).

Space Complexity

O(1) – The provided brute-force algorithm operates directly on the input collection. The process involves finding the largest number and incrementing other elements in place, without creating any new data structures whose size depends on the input. Variables used to store the largest number, the count of moves, or loop indices occupy a constant amount of extra space, regardless of the number of elements N in the collection.

Optimal Solution

Approach

Instead of simulating the process of increasing numbers one by one, we can find the solution with a simple calculation. The key insight is that increasing all but one number is the same as decreasing that one number relative to the others.

Here's how the algorithm would work step-by-step:

First, find the smallest number in the entire collection.
Imagine this smallest number is our target value that all other numbers need to reach.
For every other number in the collection, calculate the difference between it and the smallest number.
This difference represents exactly how many times that specific number would need to be 'left out' of an increase to eventually match the smallest one.
Finally, add up all these differences. The total sum is the minimum number of moves required to make all the numbers equal.

Code Implementation

def min_moves_to_equal_array(numbers_list):
    # Increasing n-1 elements is equivalent to decreasing one element, so we find the minimum element.
    minimum_number = min(numbers_list)

    total_moves = 0
    # Each number must be reduced to the minimum, and each reduction is one move.
    for current_number in numbers_list:
        # The difference between any number and the minimum is the exact number of moves for that element.
        total_moves += current_number - minimum_number

    return total_moves

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by two main operations performed on the input array of size n. First, we iterate through the entire array once to find the minimum element, which takes n steps. Following that, we iterate through the array a second time to calculate the sum of the differences between each element and the minimum element, which also takes n steps. The total number of operations is approximately n + n, or 2n, which simplifies to a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm calculates the solution using a few variables to store the minimum value and the running sum of differences. The number of these variables remains constant, regardless of the size of the input collection, which we denote as N. Therefore, the auxiliary space used is constant and does not grow with N.

Edge Cases

Case	How to Handle
Input array with only one element	The solution should return 0 as all elements are already equal and no moves are needed.
Input array where all elements are already equal	The algorithm correctly calculates the sum of differences from the minimum, which is zero, returning 0.
Input array containing negative numbers	The logic of incrementing n-1 elements remains the same, so the solution works correctly without modification.
Input array with a mix of positive, negative, and zero values	The relative differences between elements are what matter, so the presence of zeros or mixed signs is handled correctly by the standard algorithm.
Input array with large numbers, potentially causing integer overflow	The sum of differences could exceed the capacity of a standard 32-bit integer, so a 64-bit integer type (like a long) should be used for calculations.
Maximum-sized input array, leading to performance issues	An optimal O(n) solution involving a single pass to find the minimum and sum is required to avoid a timeout on large inputs.
Input array with large differences between min and max elements	Even with large differences, the mathematical insight that moves equal sum(nums) - n * min(nums) holds and prevents simulation, which would be too slow.
Input array containing duplicate values	Duplicates are handled naturally by the summation approach as each element's difference from the minimum is added independently.

Input array with only one element

How to Handle:

The solution should return 0 as all elements are already equal and no moves are needed.

Input array where all elements are already equal

How to Handle:

The algorithm correctly calculates the sum of differences from the minimum, which is zero, returning 0.

Input array containing negative numbers

How to Handle:

The logic of incrementing n-1 elements remains the same, so the solution works correctly without modification.

Input array with a mix of positive, negative, and zero values

How to Handle:

The relative differences between elements are what matter, so the presence of zeros or mixed signs is handled correctly by the standard algorithm.

Input array with large numbers, potentially causing integer overflow

How to Handle:

The sum of differences could exceed the capacity of a standard 32-bit integer, so a 64-bit integer type (like a long) should be used for calculations.

Maximum-sized input array, leading to performance issues

How to Handle:

An optimal O(n) solution involving a single pass to find the minimum and sum is required to avoid a timeout on large inputs.

Input array with large differences between min and max elements

How to Handle:

Even with large differences, the mathematical insight that moves equal sum(nums) - n * min(nums) holds and prevents simulation, which would be too slow.

Input array containing duplicate values

How to Handle:

Duplicates are handled naturally by the summation approach as each element's difference from the minimum is added independently.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the array? Can they be negative, zero, or are they strictly positive?
What are the constraints on the size of the array, `n`? For instance, what are the minimum and maximum possible number of elements?
The problem statement mentions a 'non-empty' array. Does this mean the array will always have at least one element? If so, what should be the output for a single-element array?
Are the integer values within a specific range, like the standard 32-bit signed integer range? This might be important to consider for potential overflow issues when summing elements.
Since we are incrementing `n-1` elements, could you confirm if this operation is equivalent to decrementing a single element by 1 in terms of the relative differences between elements?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if all the numbers in the collection are already the same. If they are, no moves are needed, and we're done.
If the numbers are not all equal, find the largest number in the group.
Now, take every other number in the collection (all of them except the largest one) and add one to each of them. This counts as a single move.
Keep track of how many moves you've made so far.
After making a move, go back and check again if all the numbers have become equal.
Continue this process of finding the largest, increasing the others, and counting the move, over and over, until all the numbers finally match.

Code Implementation

def min_moves_brute_force(numbers):
    number_of_moves = 0
    list_size = len(numbers)

    if list_size == 0:
        return 0

    while True:
        # This check is necessary to determine if the array elements are equal, which is our stop condition.
        all_elements_are_equal = all(element == numbers[0] for element in numbers)

        if all_elements_are_equal:
            break

        maximum_number = -float('inf')
        index_of_maximum = -1

        for current_index in range(list_size):
            if numbers[current_index] > maximum_number:
                maximum_number = numbers[current_index]
                index_of_maximum = current_index
        
        # Incrementing all elements except the max is the core logic of a single "move".
        for current_index in range(list_size):
            if current_index != index_of_maximum:
                numbers[current_index] += 1
        
        number_of_moves += 1

    return number_of_moves

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the smallest number in the entire collection.
Imagine this smallest number is our target value that all other numbers need to reach.
For every other number in the collection, calculate the difference between it and the smallest number.
This difference represents exactly how many times that specific number would need to be 'left out' of an increase to eventually match the smallest one.
Finally, add up all these differences. The total sum is the minimum number of moves required to make all the numbers equal.

Code Implementation

def min_moves_to_equal_array(numbers_list):
    # Increasing n-1 elements is equivalent to decreasing one element, so we find the minimum element.
    minimum_number = min(numbers_list)

    total_moves = 0
    # Each number must be reduced to the minimum, and each reduction is one move.
    for current_number in numbers_list:
        # The difference between any number and the minimum is the exact number of moves for that element.
        total_moves += current_number - minimum_number

    return total_moves

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array with only one element	The solution should return 0 as all elements are already equal and no moves are needed.
Input array where all elements are already equal	The algorithm correctly calculates the sum of differences from the minimum, which is zero, returning 0.
Input array containing negative numbers	The logic of incrementing n-1 elements remains the same, so the solution works correctly without modification.
Input array with a mix of positive, negative, and zero values	The relative differences between elements are what matter, so the presence of zeros or mixed signs is handled correctly by the standard algorithm.
Input array with large numbers, potentially causing integer overflow	The sum of differences could exceed the capacity of a standard 32-bit integer, so a 64-bit integer type (like a long) should be used for calculations.
Maximum-sized input array, leading to performance issues	An optimal O(n) solution involving a single pass to find the minimum and sum is required to avoid a timeout on large inputs.
Input array with large differences between min and max elements	Even with large differences, the mathematical insight that moves equal sum(nums) - n * min(nums) holds and prevents simulation, which would be too slow.
Input array containing duplicate values	Duplicates are handled naturally by the summation approach as each element's difference from the minimum is added independently.

Input array with only one element

How to Handle:

The solution should return 0 as all elements are already equal and no moves are needed.

Input array where all elements are already equal

How to Handle:

The algorithm correctly calculates the sum of differences from the minimum, which is zero, returning 0.

Input array containing negative numbers

How to Handle:

The logic of incrementing n-1 elements remains the same, so the solution works correctly without modification.

Input array with a mix of positive, negative, and zero values

How to Handle:

The relative differences between elements are what matter, so the presence of zeros or mixed signs is handled correctly by the standard algorithm.

Input array with large numbers, potentially causing integer overflow

How to Handle:

The sum of differences could exceed the capacity of a standard 32-bit integer, so a 64-bit integer type (like a long) should be used for calculations.

Maximum-sized input array, leading to performance issues

How to Handle:

An optimal O(n) solution involving a single pass to find the minimum and sum is required to avoid a timeout on large inputs.

Input array with large differences between min and max elements

How to Handle:

Even with large differences, the mathematical insight that moves equal sum(nums) - n * min(nums) holds and prevents simulation, which would be too slow.

Input array containing duplicate values

How to Handle:

Duplicates are handled naturally by the summation approach as each element's difference from the minimum is added independently.