Jobs

Interviews

Discussions

Minimum Moves to Equal Array Elements

Medium

Minimum Moves to Equal Array Elements

Medium

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 are the constraints on the size of the input array `nums`?
Can the elements of the array `nums` be negative, zero, or only positive integers?
Are there any constraints on the range of values within the `nums` array?
What should I return if the input array `nums` is empty or null?
Is the goal to find the *minimum* number of moves, or just *a* number of moves to equalize the array elements?

Brute Force Solution

Approach

The brute-force approach to this problem involves trying every possible combination of moves. We want to make all the numbers in the group the same, so we'll exhaustively explore incrementing different numbers until they all match.

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

Consider increasing one of the numbers by one.
See if that gets the numbers closer to all being the same.
If not, try increasing a different number by one instead.
Keep repeating this process of picking a number and increasing it.
Each time you increase a number, count that as one 'move'.
Continue trying different combinations of increases until all the numbers are finally the same.
Keep track of the total number of moves each combination takes.
Once you've tried all possible ways of increasing the numbers, pick the way that used the fewest moves.

Code Implementation

def minimum_moves_brute_force(numbers):
    minimum_number_of_moves = float('inf')

    def solve(current_numbers, number_of_moves):
        nonlocal minimum_number_of_moves

        # Base case: all numbers are equal
        if len(set(current_numbers)) <= 1:
            minimum_number_of_moves = min(minimum_number_of_moves, number_of_moves)
            return

        # Optimization to prune search space
        if number_of_moves >= minimum_number_of_moves:
            return

        for index in range(len(current_numbers)):
            # Try incrementing each number by one

            new_numbers = current_numbers[:]
            new_numbers[index] += 1

            # Recursively call solve with the new numbers and incremented moves
            solve(new_numbers, number_of_moves + 1)

    solve(numbers, 0)
    return minimum_number_of_moves

Big(O) Analysis

Time Complexity

O(INF) – The brute-force approach described involves exhaustively trying every possible combination of incrementing different numbers until they all match. In the worst-case scenario, the algorithm might explore an unfathomable number of combinations before finding the optimal solution or even determining that a solution is impossible within a reasonable timeframe. Because it does not make smart choices on what element to increment, it can get stuck in a loop. The number of steps could grow until it is essentially infinitely slow as it keeps checking every single possibility leading to an infinite amount of run time.

Space Complexity

O(infinity) – The brute-force approach described attempts every possible combination of moves without any limitations. The space used depends on the depth of the search tree created by exploring different increment combinations until all numbers are equal. Because no constraints are placed on the maximum number of moves, the algorithm will explore an infinite tree of possible move combinations until memory resources are exhausted, indicating unbounded auxiliary space usage. It is impossible to define the maximum stack depth of the combinations of recursive calls, as the number of moves required to equalize the array elements isn't bounded. Thus, memory use is potentially infinite.

Optimal Solution

Approach

The key insight is to focus on how each move affects the difference between the numbers. Instead of incrementing multiple numbers, consider the opposite: decrementing one number, since both achieve the same relative difference between the elements. The optimal strategy is to figure out how many times you need to decrement each element until they all equal the smallest element.

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

Find the smallest number in the set.
For each number in the set, figure out how far it is from the smallest number.
Add up all those differences. This sum is the minimum number of moves needed.

Code Implementation

def minimum_moves_to_equal_array_elements(numbers):
    minimum_number = min(numbers)

    #Find the smallest number.  All numbers must
    #eventually equal this value.

    total_moves = 0

    for number in numbers:
        #Calculate the number of moves required for
        #the current number to reach the minimum.

        difference = number - minimum_number
        total_moves += difference

    #Return the total moves needed to equalize.
    return total_moves

Big(O) Analysis

Time Complexity

O(n) – The solution first finds the minimum element in the array of size n, which requires iterating through the array once and takes O(n) time. Then, it iterates through the array again, calculating the difference between each element and the minimum element and summing these differences. This second iteration also takes O(n) time. Since we have two sequential O(n) operations, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The solution only uses a few variables to store the smallest number and the running sum of differences. The number of variables remains constant regardless of the size of the input array (N, where N is the number of elements in the input array). No additional data structures that scale with the input size are used. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 since no moves are needed on an empty array.
Array with one element	Return 0, as all elements are already equal.
Array with all elements already equal	Return 0, as no moves are required.
Array with large positive integers	The summation in the formula could lead to integer overflow; use long to store the sum or calculate the difference between each element and the minimum to avoid large sum.
Array with large number of elements (performance)	The O(n) solution based on sum and minimum element scales linearly, so it should be efficient even for large arrays.
Array containing negative numbers	The solution works correctly with negative numbers since we are only interested in the difference between the elements and the minimum.
Array with mix of large positive and negative integers	The solution is still correct because we are summing differences from the smallest element.
Integer overflow during calculation of sum or intermediate steps	Use 64-bit integers (long) to prevent overflow when summing elements or calculating differences.

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 are the constraints on the size of the input array `nums`?
Can the elements of the array `nums` be negative, zero, or only positive integers?
Are there any constraints on the range of values within the `nums` array?
What should I return if the input array `nums` is empty or null?
Is the goal to find the *minimum* number of moves, or just *a* number of moves to equalize the array elements?

Brute Force Solution

Approach

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

Consider increasing one of the numbers by one.
See if that gets the numbers closer to all being the same.
If not, try increasing a different number by one instead.
Keep repeating this process of picking a number and increasing it.
Each time you increase a number, count that as one 'move'.
Continue trying different combinations of increases until all the numbers are finally the same.
Keep track of the total number of moves each combination takes.
Once you've tried all possible ways of increasing the numbers, pick the way that used the fewest moves.

Code Implementation

def minimum_moves_brute_force(numbers):
    minimum_number_of_moves = float('inf')

    def solve(current_numbers, number_of_moves):
        nonlocal minimum_number_of_moves

        # Base case: all numbers are equal
        if len(set(current_numbers)) <= 1:
            minimum_number_of_moves = min(minimum_number_of_moves, number_of_moves)
            return

        # Optimization to prune search space
        if number_of_moves >= minimum_number_of_moves:
            return

        for index in range(len(current_numbers)):
            # Try incrementing each number by one

            new_numbers = current_numbers[:]
            new_numbers[index] += 1

            # Recursively call solve with the new numbers and incremented moves
            solve(new_numbers, number_of_moves + 1)

    solve(numbers, 0)
    return minimum_number_of_moves

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Find the smallest number in the set.
For each number in the set, figure out how far it is from the smallest number.
Add up all those differences. This sum is the minimum number of moves needed.

Code Implementation

def minimum_moves_to_equal_array_elements(numbers):
    minimum_number = min(numbers)

    #Find the smallest number.  All numbers must
    #eventually equal this value.

    total_moves = 0

    for number in numbers:
        #Calculate the number of moves required for
        #the current number to reach the minimum.

        difference = number - minimum_number
        total_moves += difference

    #Return the total moves needed to equalize.
    return total_moves

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 since no moves are needed on an empty array.
Array with one element	Return 0, as all elements are already equal.
Array with all elements already equal	Return 0, as no moves are required.
Array with large positive integers	The summation in the formula could lead to integer overflow; use long to store the sum or calculate the difference between each element and the minimum to avoid large sum.
Array with large number of elements (performance)	The O(n) solution based on sum and minimum element scales linearly, so it should be efficient even for large arrays.
Array containing negative numbers	The solution works correctly with negative numbers since we are only interested in the difference between the elements and the minimum.
Array with mix of large positive and negative integers	The solution is still correct because we are summing differences from the smallest element.
Integer overflow during calculation of sum or intermediate steps	Use 64-bit integers (long) to prevent overflow when summing elements or calculating differences.