Day 15 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#453. Minimum Moves to Equal Array Elements(M/JS)

Intro: I am a former accountant turned software engineer graduated from coding bootcamp in January 2022. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:

• Pick a leetcode problem randomly or Online Assessment from targeted companies.
• Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
• Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
• Code out the solution in LeetCode without looking at the solutions
• Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.

---

453. Minimum Moves to Equal Array Elements

It's a Math question...

Difficulty: Medium Language: JavaScript

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 <= 105
• -109 <= nums[i] <= 109
• The answer is guaranteed to fit in a 32-bit integer.

---

Solution:
My first thought was to:

• Get the difference between sum of all array element and largest number*n. That will give us the number of moves are needed to get all elements to equal to the largest number.
• Because "In one move, you can increment n - 1 elements of the array by 1"; the number of moves needed need to be divisible by n-1. If not, increase the largest number by 1 until that condition is met.
• For example, given array [1,2,3], the number of moves needed to get all element to equal to the largest number '3' is 3 (3*3 - (1+2+3)). But 3 is not divisible by n-1, 2 in this case. We increase largest number from 3 to 4. Now the moves needed for all elements to equal to largest number '4' is 6 (4*3 - (1+2+3)). 6 divided by 2 is 3. Hence, 3 moves is the answer for array [1,2,3].

User 'spacepumpkin' on LeetCode provided a much better idea:

• if we think of it the other way around, incrementing n-1 elements other than nums[i] is effectively the same as decrementing nums[i] to make all elements equal
• thus, the number of moves to increment n-1 elements is the same as the number of moves to decrement each element to get to the minimum
• I like to think of each element as a tower of blocks -- how many blocks do we have to remove so that all towers are at the minimum tower height?

ex. for [1, 2, 4], we have:
      [x]
      [x]
   [x][x]
[ ][ ][ ]  -- remove 4 blocks (x) --> [ ][ ][ ]

so, based on this way of thinking, the formula is:
number of blocks removed = (sum of all 'blocks') - (number of towers * minimum tower height)
(in our example, total # blocks = 7, number of towers = 3, & minimum tower height = 1)

Code:

function minMoves(nums) {
  let sum = nums[0];
  let min = nums[0];

//Initialize both 'sum' and 'min' variable as first number (note2)
//in the array

  for (let i = 1; i < nums.length; i++) { 

//Loop (note 1) through 'nums' array and find the total # of
//blocks and min tower height

    if (nums[i] < min) min = nums[i];

//if an element if found to be smaller than current 'min', then
//replace current value of 'min' to that smaller element found.
//To find the min tower height.

    sum += nums[i];

//add value to every element to 'sum' to get sum of all
//element(total # of blocks).

  }

  return sum - (nums.length * min);

//# blocks removed = total # blocks - (# towers * min height) <--
//refer to explation above regarding removing blocks

};

Solution Submission detail as of 2/26/2022
(Data below could vary since there are new tests/submissions daily)

• Runtime: 72 ms
• Memory Usage: 45.1 mb

---

References:
LeetCode Problem Link
LeetCode Discussion: spacepumpkin
Note 1: Loop and Iteration
Note 2: Access an array item by its index
Note 3: Addition assignment(+=)
Blog Cover Image Credit