462. Minimum Moves to Equal Array Elements II

MediumArrayMathSorting
Leetcode Link

Problem Description

The problem is to find the smallest number of moves to make all elements in an integer array nums identical. Each move consists of either incrementing or decrementing any element by 1. The goal is to figure out the minimum total number of such increments or decrements across the entire array to reach the state where every element is the same.

Understanding the problem through an example makes it easier. If nums = [1, 2, 3], we could transform all elements to 2 (the middle element) by increasing 1 by 1 and decreasing 3 by 1. This would take a total of 2 moves. If we chose any number other than 2, it would take more than 2 moves, which demonstrates that the median of the array provides the target value.

The problem specifies that the solution needs to fit within a 32-bit integer, which means we should take care to avoid integer overflows in our calculations.

Intuition

To minimize the number of moves, we need to choose a value that is in some sense central to the array since this reduces the total distance that other elements need to be moved. Mathematically, this is achieved by choosing the median of the array. The median is the central value that separates the higher half from the lower half of the data set. When all elements are moved to the median, the sum of the distances (the absolute differences) is minimized.

Here's the thinking process to arrive at the solution:

  • First, sort the array nums. Sorting brings the elements in a sequence where the median can be easily identified.
  • Next, find the median of the array, which will be the target value all elements should match. The median is located at the central index, which can be found by dividing the length of the array by two. For an even number of elements, any value between the two middle elements will work.
  • Calculate and return the sum of absolute differences between each element in the array and the median. The absolute difference ensures we count all moves, whether they're increments or decrements.

The reason this approach is efficient and correct is due to the properties of the median. It ensures the total distance for all elements to reach equality is as small as possible, which translates to the minimum number of moves.

Learn more about Math and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The implementation of the solution follows the intuition and requires understanding of sorting algorithms and efficient calculation of the central tendency (median) of the list.

Here's the step-by-step implementation walkthrough:

  1. Sorting the List: The initial step involves sorting the list of numbers. This can be done through any efficient sorting algorithm. Python's built-in sort function is typically implemented as Timsort, which has a time complexity of O(n log n).

    1nums.sort()

  2. Finding the Median: After sorting, the median is the middle element of the sorted list if it has an odd length. Otherwise, it is any value between the two middle elements if the list has an even length. Since we are interested in the number of moves, we can select either of the middle elements as our target for an even-length array. In the code, the median is found by taking the element at index len(nums) >> 1. The >> is a right shift bitwise operator which in this context is equivalent to integer division by 2.

    1k = nums[len(nums) >> 1]

  3. Calculating the Moves: The total number of moves is the sum of the absolute differences between each element in the sorted list and the median. The abs function is used for obtaining the absolute value. This part takes advantage of the fact that the median minimizes these differences.

    1return sum(abs(v - k) for v in nums)
  • The data structure used in this solution is the given list nums.
  • The algorithm used includes a sorting technique to order the elements, followed by a linear scan to calculate the total moves.
  • The pattern utilized here is finding a value to minimize the sum of distances which is a classical optimization strategy.

The reason why these particular choices were made in the approach is because sorting the list first simplifies the determination of the median. Once the list is sorted, elements below the median are all smaller and those above are all bigger. Thus, when each element is moved to the median, the total number of moves is minimized. Since we are interested in the magnitude of the changes rather than the direction, we use absolute values.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example Walkthrough

Let's consider the array nums = [1, 5, 2, 4].

  1. Sorting the List: Initially, we sort the array nums. After sorting, it looks like this: [1, 2, 4, 5].

    1nums.sort()  # results in nums being [1, 2, 4, 5]

  2. Finding the Median: Since the array has an even number of elements (4 elements), any value between the two middle elements can be used. Here, we can choose either 2 or 4. For simplicity, and following the approach, we'll select the lower index, so our target is 2.

    1k = nums[len(nums) >> 1]  # results in k being 2

  3. Calculating the Moves: We calculate the sum of absolute differences between each element and k, our median value, which in this case is 2.

    1moves = sum(abs(v - k) for v in nums)  # moves is abs(1-2) + abs(2-2) + abs(4-2) + abs(5-2)

    This gives us 1 + 0 + 2 + 3 = 6 moves. Thus, to make all elements in the array identical, we need a minimum of 6 moves in this case:

    • Element at index 0: 1 must be incremented by 1 to become 2 (1 move)
    • Element at index 1: 2 is already 2, so no moves needed (0 move)
    • Element at index 2: 4 must be decremented by 2 to become 2 (2 moves)
    • Element at index 3: 5 must be decremented by 3 to become 2 (3 moves)

To summarize, our optimal solution involves incrementing and decrementing elements to turn [1, 2, 4, 5] into [2, 2, 2, 2] with a minimum of 6 moves.

Solution Implementation

1class Solution:
2    def minMoves2(self, numbers: List[int]) -> int:
3        # Sort the list of numbers to find the median more easily
4        numbers.sort()
5
6        # Calculate the median by taking the middle element after sorting
7        # Note: 'len(numbers) >> 1' is the bitwise right shift operation, equivalent to 'len(numbers) // 2'
8        median = numbers[len(numbers) // 2]
9
10        # Calculate the minimum number of moves required by summing up the absolute differences
11        # between each number and the median
12        # The absolute difference represents how far each number is from the median,
13        # summing them up gives the minimum moves to equalize the numbers
14        total_moves = sum(abs(number - median) for number in numbers)
15
16        # Return the total number of moves
17        return total_moves
18
1class Solution {
2    public int minMoves2(int[] nums) {
3        // Sort the input array
4        Arrays.sort(nums);
5
6        // Find the median of the array which will be our target number
7        // Using bitwise right shift for finding the mid element (equivalent to dividing by 2)
8        int median = nums[nums.length >> 1];
9
10        // Initialize the number of moves required to bring all elements to the median
11        int moves = 0;
12
13        // Calculate the total number of moves required
14        // by summing up the distance of each element from the median
15        for (int num : nums) {
16            moves += Math.abs(num - median);
17        }
18
19        // Return the total number of moves
20        return moves;
21    }
22}
23
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to find the minimum number of moves required to make all the array elements equal,
7    // where a move is incrementing or decrementing an element by 1.
8    int minMoves2(std::vector<int>& nums) {
9        // First, we sort the input array.
10        std::sort(nums.begin(), nums.end());
11      
12        // Find the median of the array. This will be the target value for all elements.
13        // Since we're making all values equal to this target,
14        // it minimizes the total number of moves required.
15        int median = nums[nums.size() / 2];
16
17        // Initialize the answer variable to accumulate the total moves needed.
18        int totalMoves = 0;
19
20        // Iterate over the array, adding the absolute difference between
21        // each element and the median to our total moves.
22        // This gives us the total moves required to make each element equal to the median.
23        for (int value : nums) {
24            totalMoves += std::abs(value - median);
25        }
26      
27        // Return the total number of moves to make all elements equal.
28        return totalMoves;
29    }
30};
31
1/**
2 * This function calculates the minimum number of moves required to
3 * make all array elements equal. A single move is incrementing or
4 * decrementing an array element by 1.
5 *
6 * @param {number[]} numbers - The array of integers.
7 * @return {number} - The minimum number of moves to make all elements equal.
8 */
9function minMoves2(numbers: number[]): number {
10    // Sort the array in ascending order so that we can find the median.
11    numbers.sort((a, b) => a - b);
12
13    // Find the median of the array, which is the middle element after the sort,
14    // or the average of two middle elements if the array has an even number of elements.
15    // This median will be the target value for all elements.
16    const median = numbers[numbers.length >> 1]; // '>> 1' is equivalent to dividing by 2 but faster.
17
18    // Reduce the array, accumulating the total moves needed by adding the absolute
19    // differences between each element and the median.
20    return numbers.reduce((totalMoves, currentValue) => totalMoves + Math.abs(currentValue - median), 0);
21}
22
Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

Time Complexity

The provided Python code involves sorting an array and then iterating through the sorted array once.

  1. The nums.sort() function has a time complexity of O(n log n), where n is the length of the list nums. This is because the sorting algorithm used by Python's sort function (Timsort) has this time complexity for sorting an average list.

  2. The list comprehension sum(abs(v - k) for v in nums) iterates through the sorted list exactly once to compute the absolute differences and sum them up, which has a time complexity of O(n).

When combining both steps, the dominant factor is the sorting step, so the overall time complexity is O(n log n).

Space Complexity

The space complexity of the code is determined by the additional space used beyond the input size.

  1. The sort() method sorts the list in place and does not require additional space proportional to the size of the input list, so the space complexity for this step is O(1).

  2. The computation of the sum using a generator expression also does not require space proportional to the input size since it computes the sum on the fly.

Therefore, the total space complexity of the provided solution is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫