Avoiding My Mistakes!! - Shifting Zeros Problem

okay so we need to create a python function that will take a list of integers as an input and it takes each Zero from that list and it shifts it to the end of the list so every nonzero integer keeps that same order but all the zeros get moved to the end of the list okay so I've got a pretty simple idea in my head of how I want the function to work so basically I just want to iterate through each element of the list and if that element is a zero I want to remove it from the list and append a zero to the end of the list so that by the time I iterate through each element all the zeros should be moved to the end all right so let's write this down in Python so let me Define the function here and let's call it funk with array as the input now for I and array if I is equal to zero then we want to array. remove I and then we can append it back to the end of the list by saying array. append 0o okay and then we can just return array here all right so let's test this out so let's create a list here and we'll print the output here okay let's run this and there we go we got all the zeros shifted to the end okay but let's really put our function to the test and see just how efficient it is so first let's import random then we'll import time then let's set the variable in to some large number and what I want to do is create a random array that contains integers from 0 to 9 that is length in okay so now let's create a start time so let's say start is equal to time. time then let's call our function with our massive list as the input and then after the function is complete let's get our stop time here and then let's print our stop time minus our start time to get the total time all right so let's run that all right so that took 26 seconds to run but I think we can do better let's take a closer look at our logic to see if there's anywhere we can make some improvements all right so after thinking about this for a bit I think I understand what's going on here when we iterate through each element of the list when we see a zero and remove it python then has to shift every item that comes after it to fill its place that means removing items from the list gives us the worst case time complexity of Big O n so if we take a look at our function the fact that We're looping through each item in our list that by itself already gives us a Time complexity of Big O N and as we just saw each time we remove an item from the list that's another Big O of n time complexity and since we have a big O of n inside of another Big O of n our function has a total time complexity of Big O of n squ on top of that we're also appending an item after it's removed from the list so for every Loop iteration we're still working with a massive list of length n okay so to avoid removing elements from the list within the for Loop let's take a different approach what I want to do instead is I'm going to set a temporary empty list outside of the for Loop I also want to keep count of how many zeros we have in the list so I'll set a variable equal to zero here to keep count now as we Loop through the list if it's a nonzero element I want to append that element to the temporary list appending to a list has the time complexity of Big O one so we're good there and if we encounter a zero in the list we want to add one to our zero counter after we've Loop through each element of our list we now want to take our temporary list up here and add a list of zeros at the end equal to the number of zeros we counted so we get this as our output all right so let's go back to our script and implement this new approach so let's first create a temporary empty list here and then let's keep count of how many zeros we have all right so now let's say for I in Array and if I is not a zero we want to append I to our temporary list else if it is a zero we want to increment our counter and then after we've looped through each element we can do t. extend Z * a single valued list with a zero inside so then we can just return T here okay so examining the time complexities here we know our for Loop gives us an automatic Big O of n this t. aend operation is only a big O of one and incrementing Z here as well and then this extend operation is a big O of n but since it's outside of the four Loop it doesn't compound the time complexity to n s so looking at all these our overall time complexity for this function is just Big O of n all right so Moment of Truth here let's see if we get an improvement on our last runtime so let's run this and wow look at that 9 milliseconds that's an impressive Improvement compared to the 26 seconds we got earlier all right so yeah I'd love to see what kind of solutions you guys come up with so be sure to join the Discord and share with us link below if you like

this video be sure to show some love to the like button also big thanks to the bike club members for supporting me thanks for watching and I'll see you all in the next video