Jobs

Interviews

Discussions

Minimum Moves to Equal Array Elements II

Medium

Asked by:

51 views

Topics:

ArraysGreedy Algorithms

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 or decrement an element of the array by 1.

Test cases are designed so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

Example 2:

Input: nums = [1,10,2,9]
Output: 16

Constraints:

n == nums.length
1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Minimum Moves to Equal Array Elements II

Medium

Asked by:

51 views

Topics:

ArraysGreedy Algorithms

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 or decrement an element of the array by 1.

Test cases are designed so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

Example 2:

Input: nums = [1,10,2,9]
Output: 16

Constraints:

n == nums.length
1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

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 input array `nums`? Can they be negative, zero, or very large?
What is the maximum size of the input array `nums`?
If the input array `nums` is empty or null, what should the function return?
Are we guaranteed that the array will always contain integers, or could there be other data types?
Are there any specific constraints on the magnitude of the minimum number of moves? Should I be concerned about potential integer overflow issues when calculating the total moves?

Brute Force Solution

Approach

The brute force method for this problem involves trying out every single number as the target to which all other numbers in the list will be changed. We calculate the number of moves needed for each potential target and find the lowest number of moves overall.

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

Consider each number as a potential final value for all the numbers in the list.
For each of these potential final values, go through the entire list and calculate how many moves it would take to change each number in the list to that potential final value. The number of moves for each number is simply the difference between the number and the potential final value.
Add up all the individual move counts to get the total moves needed for that potential final value.
Repeat this process for every possible final value.
After checking every possible final value, compare the total move counts. Pick the lowest total move count. That's the answer.

Code Implementation

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

    # Consider each number as a potential final value.
    for potential_final_value in numbers:

        total_moves_for_final_value = 0

        # Calculate moves needed to change each number to potential final value.
        for number in numbers:
            total_moves_for_final_value += abs(number - potential_final_value)

        # Update minimum moves if current potential final value yields fewer moves.
        minimum_number_of_moves = min(minimum_number_of_moves, total_moves_for_final_value)

    return minimum_number_of_moves

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each element of the array as a potential target value. For each target value, the algorithm iterates through the entire array again to calculate the moves needed to transform each element to the target value. Thus, for an array of size n, we have n iterations where each iteration takes O(n) time to compute the moves. The total time complexity is therefore O(n * n) = O(n²).

Space Complexity

O(1) – The brute force approach iterates through each number in the input array of size N as a potential target value. For each target value, it iterates through the same array again to calculate the moves required. However, it only stores a few variables like the current target, the current element being compared, the move count for each element, and the total move count for the current target. These variables occupy constant space, irrespective of the size of the input array. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The trick to this problem is realizing that all the numbers should move towards a single meeting point to minimize the total movement. The best meeting point is the middle number once you sort the list.

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

First, put the list of numbers in order from smallest to largest.
Find the middle number in the sorted list. If there's an even number of numbers, take the average of the two middle numbers or either of them.
For each number in the original list, calculate how far it needs to move to reach the middle number.
Add up all the distances you calculated in the previous step. That sum is the smallest total amount of movement needed to make all the numbers equal.

Code Implementation

def minimum_moves_to_equal_array_elements_ii(numbers):
    numbers.sort()

    # The median is the optimal meeting point to minimize total moves
    list_length = len(numbers)
    median_index = list_length // 2
    median_value = numbers[median_index]

    total_moves = 0
    for number in numbers:
        # Sum the absolute differences from each number to the median
        total_moves += abs(number - median_value)

    return total_moves

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this algorithm is sorting the input array of size n. Common sorting algorithms, such as merge sort or quicksort, have a time complexity of O(n log n). Finding the median takes O(1) time because it's just accessing an element in the sorted array. Calculating the sum of absolute differences from each element to the median involves iterating through the array once, which takes O(n) time. Since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity

O(1) – The space complexity is dominated by the sorting algorithm's auxiliary space. While the plain english explanation doesn't specify the sorting algorithm, assuming an in-place sort like heapsort or insertion sort is used, the auxiliary space is constant. The only additional space used consists of a few scalar variables (for the median and the accumulated sum), which take up constant space regardless of the input size N. Therefore, the overall auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 if the input array is empty or null, as no moves are required.
Array with a single element	Return 0 if the array has only one element, as it is already equal to itself.
Array with all elements being the same	Return 0 as no moves are needed to make all elements equal.
Array with positive and negative numbers	The algorithm should correctly calculate the moves needed irrespective of the sign of the numbers, as it finds the median and calculates absolute differences.
Array with very large numbers (close to integer limits) that might cause overflow during summation	Use long data type to store intermediate sums of differences to prevent integer overflow.
Array with many duplicate numbers	The median calculation and move calculation handle duplicate numbers correctly.
Large input array affecting performance	Using a linear time median finding algorithm (e.g., quickselect or using the nth_element method) ensures efficient performance for large inputs, avoiding O(n log n) sorting.
Array where the median is not an integer	When the array size is even, calculate the median as the average of the two middle elements; since all moves are integer, either of the two middle elements will yield the optimal result.

Empty or null input array

How to Handle:

Return 0 if the input array is empty or null, as no moves are required.

Array with a single element

How to Handle:

Return 0 if the array has only one element, as it is already equal to itself.

Array with all elements being the same

How to Handle:

Return 0 as no moves are needed to make all elements equal.

Array with positive and negative numbers

How to Handle:

The algorithm should correctly calculate the moves needed irrespective of the sign of the numbers, as it finds the median and calculates absolute differences.

Array with very large numbers (close to integer limits) that might cause overflow during summation

How to Handle:

Use long data type to store intermediate sums of differences to prevent integer overflow.

Array with many duplicate numbers

How to Handle:

The median calculation and move calculation handle duplicate numbers correctly.

Large input array affecting performance

How to Handle:

Using a linear time median finding algorithm (e.g., quickselect or using the nth_element method) ensures efficient performance for large inputs, avoiding O(n log n) sorting.

Array where the median is not an integer

How to Handle:

When the array size is even, calculate the median as the average of the two middle elements; since all moves are integer, either of the two middle elements will yield the optimal result.

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 input array `nums`? Can they be negative, zero, or very large?
What is the maximum size of the input array `nums`?
If the input array `nums` is empty or null, what should the function return?
Are we guaranteed that the array will always contain integers, or could there be other data types?
Are there any specific constraints on the magnitude of the minimum number of moves? Should I be concerned about potential integer overflow issues when calculating the total moves?

Brute Force Solution

Approach

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

Consider each number as a potential final value for all the numbers in the list.
For each of these potential final values, go through the entire list and calculate how many moves it would take to change each number in the list to that potential final value. The number of moves for each number is simply the difference between the number and the potential final value.
Add up all the individual move counts to get the total moves needed for that potential final value.
Repeat this process for every possible final value.
After checking every possible final value, compare the total move counts. Pick the lowest total move count. That's the answer.

Code Implementation

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

    # Consider each number as a potential final value.
    for potential_final_value in numbers:

        total_moves_for_final_value = 0

        # Calculate moves needed to change each number to potential final value.
        for number in numbers:
            total_moves_for_final_value += abs(number - potential_final_value)

        # Update minimum moves if current potential final value yields fewer moves.
        minimum_number_of_moves = min(minimum_number_of_moves, total_moves_for_final_value)

    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:

First, put the list of numbers in order from smallest to largest.
Find the middle number in the sorted list. If there's an even number of numbers, take the average of the two middle numbers or either of them.
For each number in the original list, calculate how far it needs to move to reach the middle number.
Add up all the distances you calculated in the previous step. That sum is the smallest total amount of movement needed to make all the numbers equal.

Code Implementation

def minimum_moves_to_equal_array_elements_ii(numbers):
    numbers.sort()

    # The median is the optimal meeting point to minimize total moves
    list_length = len(numbers)
    median_index = list_length // 2
    median_value = numbers[median_index]

    total_moves = 0
    for number in numbers:
        # Sum the absolute differences from each number to the median
        total_moves += abs(number - median_value)

    return total_moves

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 if the input array is empty or null, as no moves are required.
Array with a single element	Return 0 if the array has only one element, as it is already equal to itself.
Array with all elements being the same	Return 0 as no moves are needed to make all elements equal.
Array with positive and negative numbers	The algorithm should correctly calculate the moves needed irrespective of the sign of the numbers, as it finds the median and calculates absolute differences.
Array with very large numbers (close to integer limits) that might cause overflow during summation	Use long data type to store intermediate sums of differences to prevent integer overflow.
Array with many duplicate numbers	The median calculation and move calculation handle duplicate numbers correctly.
Large input array affecting performance	Using a linear time median finding algorithm (e.g., quickselect or using the nth_element method) ensures efficient performance for large inputs, avoiding O(n log n) sorting.
Array where the median is not an integer	When the array size is even, calculate the median as the average of the two middle elements; since all moves are integer, either of the two middle elements will yield the optimal result.

Empty or null input array

How to Handle:

Return 0 if the input array is empty or null, as no moves are required.

Array with a single element

How to Handle:

Return 0 if the array has only one element, as it is already equal to itself.

Array with all elements being the same

How to Handle:

Return 0 as no moves are needed to make all elements equal.

Array with positive and negative numbers

How to Handle:

The algorithm should correctly calculate the moves needed irrespective of the sign of the numbers, as it finds the median and calculates absolute differences.

Array with very large numbers (close to integer limits) that might cause overflow during summation

How to Handle:

Use long data type to store intermediate sums of differences to prevent integer overflow.

Array with many duplicate numbers

How to Handle:

The median calculation and move calculation handle duplicate numbers correctly.

Large input array affecting performance

How to Handle:

Using a linear time median finding algorithm (e.g., quickselect or using the nth_element method) ensures efficient performance for large inputs, avoiding O(n log n) sorting.

Array where the median is not an integer

How to Handle:

When the array size is even, calculate the median as the average of the two middle elements; since all moves are integer, either of the two middle elements will yield the optimal result.