Move Zeroes - LeetCode 283 - JavaScript

Step by step walk through of the solution to the popular Meta coding interview question, Move Zeroes.

LeetCode 283

JavaScript

0:00 Intro
0:28 Explanation
1:25 Code

#softwareengineering #javascript #leetcode

[syedhxssam]

it works why people are saying in the shorts that it don’t.

[eugenekalashnikov]

Thanks, I didn't know that we may flip values in an array this way. Usually I did it via an intermediate variable

[shadowingyou]

Hmm.. Why not increase the array size when we find a zero? Then swap the located 0 element with the newly created last element of the array - delete the new 0 you just swapped and repeat this process? You go through the array once, keep the order, but still have to go through every single element.

So [0, 1, 0, 3, 12] => [0, 1, 0, 3, 12, 0] --> Swap a[0] and a[5], delete a[0].
Next [1, 0, 3, 12, 0]. Keep going through the array and repeat that process. 1 != 0, so you look at a[1] next, add an element to the array, swap, delete, and keep going through the array for more 0's.

No matter what, you have to go through every element to find a 0, that's unavoidable. Especially since this is unsorted.
You technically move the elements as required, you stayed within the constraints, and limited the amount of operations required. In this case, I'll do 2 additions to array, 2 swaps, 2 deletes in array, and [L - 0 count] array searches. As I was typing this, I realized I left an infinite loop at the end, so we have to track how many 0's were counted and make sure we go to the length of array - number of 0's moved to the end.
Every time you delete the element you swapped, it is an unassociated with the original element values.

This is to track an array which could be 100's elements long, not 6. Brute force is better when it's shorter. So If I have an array of 100 with five 0's scatters. I will have 100 - 5 (95) element searches, 5 additions to array, 5 moves, and 5 deletes to array.
The method used here would be all 100 element searches, but twice because of two variables and a comparator each time. An unknown but greater than 5 moves of values.

At least, this is my thought process.

[eirikwitt]

Hi, just thought I'd let you know that this is not the most optimal solution as you state in the video. I also think you misunderstood the followup question. By minimize operations done, they do not mean different operations, but operations in total when executing the program. In the worst case for your algorithm, (a list with only one 0 at the beginning), you would move the 0 through every single index in the array resulting in 2n write operations. A better solution would be to keep track of how many zeroes you have seen and write them all at the end, resulting in only n write operations.