The first approach is terrible, although it works by accident. Mutating array during iteration is a bad idea; it skips the next item after you removes the current item (this can be seen by adding a print statement to the loop). It works because it do enough time of remove/append. When I saw your title and cover I thought you were talking about this...
I had encountered the problem you are mentioning here, around 2 years ago and it took me a month for find and remove it. I have to say it was a nightmare. now I see the code that does that I'm scared to death.
Another easy optimization might be to populate t with zeroes. Then appending each time won't have to create another copy if overflown. It also has the added bonus that you don't have to extend with zeroes. ``` def func(array): t=len(array)*[0] i=0 for e in array: if e: t[i]=e i+=1 return t ```
unless python has some kind of optimization here len(array) * [0] would loop as populating it requires you to well loop and add each value, making it O(n²)
This is slower in Python. While it is good practice in all other languages to allocate the correct amount of memory for the array. In Python the first line "t = len(array)*[0]" takes O(n), all the way to n. Then the for loop also goes all the way to O(n). Making the final time O(2n). Compared to b001's solution: There the total is O(n + z) where z is the number of zeros in array and z < n. In the worst case z == n, so it goes to O(2n), but shawon's solution is O(2n) every time. When z
You could use a list comprehension in the form of a filter t = [x for x in array if x != 0] The complexity would be the same but a list comprehension would be computationally faster than the call to append. The counter can simply be replaced by the difference in length between t and the original array.
after trying a few things, ive found this to be the fastest solution. It takes 0.04s on average for an array 1m integers long, compared to the video's solution that takes about 0.05s for me.
b001, your production quality is always fantastic. This is my favourite video of yours so far. I like the flow of the different steps -- hearing your plan of attack, watching your solution, then exploring an optimisation. You teach so much in such a short amount of time. Cheers.
I was just wondering if there'd be a way to do this! I'm guessing this'd also be super fast in C, since accessing an array in C is just a single pointer dereference, where as shifting memory on the stack or (even worse) allocating / deallocating it on the heap is relatively slow.
We sacrificed memory for time improvement here. You can achieve a huge improvement without sacrificing memory by iterating by index and using the .pop method.
I would say that it's a coincedence that first code is working at all. When you remove an element from the list you are iterating over, result is rather unpredictable and depends on current implementation of the list (and could change between version). If you alter the task slightly and ask to just remove all the zeroes instead of moving them to the end and try to solve it by the same code with "array.append(0)" line commented, it'won't be just slow, **it would break the data** (currently). So, algorithm complexity is the least important problem with such approach, it has a huge potential of being buggy. For this specific task you could do it in linear time inline with an iterator and a counter (as was already mentioned in comments), or with something like `return (res := [x for x in array if x != 0]) + [0] * (len(array) - len(res))` (or spread it over 3 lines if you are afraid of walrus :-) ) Additionally, there is a common method for tasks like that, when you need a complex rules of sorting: ` return sorted(array, key=lambda x: (False, x) if x != 0 else (True, 0))` Basically, usage of tuples for key function in sort allows you to specify a hierarchy of elements and give a special treatment for zeroes in this case. Complexity is nlogn, but for not so big lists it shold be fine and universal solution.
You can also solve this problem using the two pointer approach: def func(arr: list[int]) -> list[int]: try: lt = arr.index(0) except ValueError: return arr rt = lt + 1 while rt < len(arr): if arr[rt] != 0: arr[lt] = arr[rt] lt += 1 rt += 1 while lt < len(arr): arr[lt] = 0 lt += 1 return arr The advantage of this approach is that that you’re not creating a new array, so memory is constant.
@@hallooww sorting is slower. Albeit not much slower in Python specifically, given sorting is built-in and, like most built-in functions in Python, is mostly written in C. But in general a quick sort is O(n log n), whereas this algorithm is O(n).
@AWriterWandering, from the stable sort of timsort which handles false boolean values by placing them at the end, particularly benefiting from Python's binary optimizations, what are you even arguing? asserting that a try block with index() is optimal shows your incompetence, especially considering the comparable efficiency of if 0 in arr (both O(n) operations), along with the additional overhead introduced by the try block.
Absolutely proud of myself for figuring out the more efficient way of doing it as soon as I saw the first method. No, I won't accept being told how simple the problem was-
Ikr, although my reason for doing it that was was a fear of skipping over any values in the for loop, a fear that has stuck with me since I learnt list comprehension instead of using the index
This can also be done on the same reserved list without duplicating memory. You just have to maintain a couple of position integers. Loop all the list through the read position. When a zero is encountered increment the read position. When a non zero is encountered copy the value from the read position to the write position and incremento both. To finish up fill from write+1 to the end with zeroes
An *excellent* solution. Saves memory and CPU time. You need to be careful about whether to fill, and how much. Here's an example of how to avoid unwanted filling: def sortem(nums): if len(nums) < 1 or not isinstance(nums[0], int): return wptr = 0 for rptr in range(len(nums)): if nums[rptr] == 0: continue nums[wptr] = nums[rptr] wptr += 1 if wptr and wptr < len(nums): # Only fill if we found both zeros and non-zeros for i in range(wptr,len(nums)): nums[wptr] = 0 return
You can simply swap first encountered non-zero with the first encountered zero, which is even more optimal, as it doesn't use external space. I am not using python at all, so it can be probably written more "pythonically", but this is the basic idea: def shift_zeros(array): last = 0 for i, num in enumerate(array): if num: array[i], array[last] = array[last], array[i] last += 1 return array
Nice solution! We had a discussion in the discord and I think we finalized a pretty elegant solution: def shift_zeros(array): return [*filter(None, array] + [0]*array.count(0)
@@RandomGeometryDashStuff return [*filter(None, array)] + [0]*array.count(0) he just forgot to write a bracket, of the filter function, but the idea is good
yeah this was my first though as well, although you can probably do better with built-ins since those are in c instead of python, but that's a bit of a cheat code :)
@@b001 I got this version to perform better by ~15%: lambda array: [*filter(None, array), *(array.count(0)*[0])] This is probably not worth the degredation in readibility though
You can also use the divide and conquer technique, though it wouldn't be as efficient, but it will save you the space complexity. First split the array until you reach a base case of 1 or 2 elements, and swap the first element with the second if the first is a zero, else do nothing - then when merging the two arrays, you already have them with ending 0s, so you simply can combine them in a similar manner to merge sort. Merging two arrays is O(n), and splitting will be O(logn), so the time complexity is O(nlogn). But because you can do this in place, the space complexity is O(1).
It's a bit unecessary to create a whole new array, since it can become costly for large n. Instead you could iterate over the array and keep track of the leading zero. As soon as you find an element which is non-zero, you simply swap the zero and the element and increment the "leading zero index" by one. This solution will have O(n) timecomplexity and O(1) space complexity.
This solution sounds interesting to me, but I’m not sure if I understand completely. With “leading zero” do you mean the first zero you encounter in the list at that point in time? Because it sounds like this solution would slot a lot of numbers in slots previously occupied by zeros which could be randomly distributed trough the list and thus these numbers would be randomly distributed as well. Thus creating a very different list of numbers and not fulfilling the promise of only moving the zeros to the end. Please do correct me if I misunderstood :)
@helboy1111 yes exactly, with leading zero I mean the first zero encountered in the list. Imagine the following example: { 1, 0, 0, 2, 0, 3 } We iterate over the list above with a variable X as our index. We find the first zero at X = 1 so we store that in a variable Y. If we move forward through the list until we find the 2 when X = 3 we can safely swap the values at index X and Y to produce the following intermediate list: { 1, 2, 0, 0, 0, 3 } As you can see, we have not changed the relative order of the non-zero numbers. Now we simply increment Y because we know that the following number MUST be a zero (or outside the list). This is so because we swap as soon as we find the first non-zero value and even if it was located at the index immediately after Y (that is Y+1) then we would have just moved a zero to that position! After performing the swap we can continue iterating over the list until we reach the end, repeating the swap-and-increment procedure for every non-zero value found. Hope this clears it up :)
@@BeholdTheDevil Ah thanks a lot, this clears up my confusion completely. It wasn't clear to me before that you would only take non-zero elements after the leading zero. Which makes sense in hindsight, considering the well-named "leading zero".
Good solution. However, consider [1,0,2,3,4], in which the 2,3 will be updated to 0 only to be overwritten again. Since there will a lot more non-zeroes, this becomes quite inefficient. Instead assume the swapped non-zero becomes 0 and then after the last "swap", update to 0 the elements after the leading zero index. So worst case each element is updated once.
@@badhombre4942 I suppose that is a valid point. There is really no need to write the zeroes before the end. Although I doubt this would have any major performance penalty, as a register swap can be done in a single cycle CPU instruction, it would be interesting to see if it made a difference.
I used the same idea, but with list comprehension and the count method def func(array): t = [i for i in array if i != 0] z = array.count(0) t.extend(z * [0]) return t
@@TehKarmalizer Actually you're right. Python stores the length of a list as metadata with the list and updates it when the list is modified, so __len__() call is O(1). My bad.
I though about the second solution instantly, but for a different reason, I would never append or remove elements from an array while iterating thru it, creating a new array is safer...
Any opportunity not to use loops should be utilized . A simple list comprehension over the list if != 0, inserted at the beginning if a zero array or padded with zeros.
@@0LoneTech the way I’m doing the inventory system in my game has two parts, the items and the non-item slots. I do use this method to update the inventory every frame so that it returns whatever items to the top that I may have accidentally misplaced using my placer variable. I believe arrays_sort() requires a function to work properly which is why I haven’t really used it yet as I’m still learning what that would even mean. So yes, I acknowledge the difference, but I think I just used the wrong terminology to describe my inventory system.
My personal intuition on how to do this in-place in O(n) time is to iterate forward in the array until a zero is reached, then iterating backwards until a nonzero is reached, switching the values, continuing to repeat until the two indices meet in the middle.
If I understand your solution correctly, I think it does not work. Take 1,0,2,3 as the input, you solution will produce 1,3,2,0 but it is supposed to be 1,2,3,0
Your final solution use extra memory (temporary array of n elements). I have an idea how to improve first method. Instead of appending and removing elements from array, just replace items instead. Create 2 pointers, first is a start of an array, second is last element. Then go through array using 1st pointer. If number is not 0, increment 1st pointer. Else swap that zero with 2nd pointer and subtract 1 from 2nd pointer. Continue untill 2 pointers point on the same element.
I am at 2:22 and I want to see if I can figure it out myself. At first, I would create a new list and a "zero-counter". When looping through the list, if the number is a non-zero digit (1-9), I append it to the new list. Else, if it's 0, I increase the zero counter by 1. At the end of the loop, once all positive numbers have been placed in the list, I make a for loop with a range(zero_counter), which will append the same amount of zeroes to the final list as the amount there were on the original list. Now return that list.
It works but you would need 2x the memory. One approach would keep a record of zero's indexes of the list if you expect it to have fewer zeros then items, then you can shift everything after. you can use generators too that's a great middle term
In put of simple termes this could be used to other codes If your code has to go around the road to go to it's destination it will take longer but if it takes longer to think and pick a shorter way it will go to it's destination faster So if anyone's code is slow maybe you can try to imagine it differently on how it could go faster like he did right here
My first instinct was merely to make 2 empty arrays, append to array 1 if != 0, else append to array 2, then concatenate two lists outside loop, and return.
def swap(array, i, j): array[i], array[j] = array[j], array[i] def func(array): i = 0 for j in range(len(array)): if array[j] != 0: swap(array, i, j) i += 1 return array
my first approach was close to your second aka making a temp array and a zero counter. however instead of multiplying zeros to the end using extend i just made a nother for loop and apanded the zeros to the end.
Rather than creating a loop, I would create a list (temp) with list comprehension: temp = [i in array if i != 0] Or transform it into a set and get the difference temp = list(set(array) - {0}) # only works if the original array does not have replicates And comput z which is the difference between the length of the two lists: z = len(array) - len(temp)
Technically O(2N + C), there are more operations that are happening so we just go with C and it's so small that it doesn't even matter. I would like to point out your use of space that wasn't covered. I really do think you could do an in place change to the list without having to sacrifice additional space. Space appears to be O(2N) as well. If this where billions of integers we would have to allocate twice the size, arguably it's fine, but in a MAANGT interview I can see a hiring manager getting amped about that.
def func(array): x = list(filter(None, array)) y = list(filter(lambda s: s == 0, array)) return x + y i think this solution also can pretend to be good
UPDATE #2: So I've found an even faster method. On my PC this method is faster than the list comprehension method I've tested even though the doc's indicate they should be equivalent: def test_filter_method(input): filtered = list(filter(None, input)) return filtered + ([0] * (len(input) - len(filtered))) This seems to be about the limit you can go with speed on this problem and I'm not sure I'm going to find a faster way. UPDATE: This really piqued my curiosity so I decided to time a few methods and come to some interesting conclusions. The first method I tried was to see if the sort function could do this, and yes it can. Using a lambda like here: def test_lambda(input): return sorted(input, key=lambda x: 1 if x == 0 else 0) def test_lambda_in_place(input): input.sort(key=lambda x: 1 if x == 0 else 0) return input both methods are slightly slower than the list comprehension method I mention below. But if you want to keep your space complexity lower it is very good and I wouldn't blink at using this. I did find a faster way though. After reading through some of the docs you can provide a constructor to the key argument in sort and, exploiting some of the nuances of the problem at hand, you can do this: def test_constructor(input): return sorted(input, key=bool, reverse=True) def test_constructor_in_place(input): input.sort(key=bool, reverse=True) return input Both of which take nearly the same test time of my original list comprehension method, if not lower in some cases. Incredible really. So the take away, if you can do use pythons constructors and basic types, and sorting is fast very very fast. ----- Old Post ---- The way i would do it is using list comprehension a list multiplication: def test_list_comprehension(input): filtered = [x for x in input if x != 0] return filtered + ([0] * (len(input) - len(filtered))) In general list comprehension is very fast especially for such simple filters and list multiplication is extremely fast so I would expect this to be near optimal. For those that also are talking about space complexity you can always keep the time complexity below O(2n) with a constant space complexity by doing the following: def test_naive_in_place(input): ins = 0 for i in range(len(input)): if input[i] != 0: input[ins] = input[i] ins += 1 for i in range(ins, len(input)): input[i] = 0 return input This approach will be considerably slower however and should be avoided unless you're dealing with HUGE lists. Even then an iterable or another solution may be better.
a stupid but easy way is to make a new array, loop through the first array and just insert all the regular integers and then once that's done, fill the rest of the list with zeros (if they aren't already initialized to zeros anyway), then if it NEEDS to be in the first array, just write each value of the new array to the original.
if this was a question during an interview, the answer most likely would not be consider complete, as most likely, the interviewer would ask you to rewrite the program as to Not use an additional memory O(n) in this case, but manipulate the existing array.
Yes this is my immediate solution too, but be mindful of what it's doing,. you are trading time complexity for space complexity, you are basically doubling the allocation in memory since you are creating a new array of N at the end.
I tried writing an in place solution: def run(arr): try: zeros: int = 1 for i in range(arr.index(0)+1, len(arr)): if arr[i] == 0: zeros += 1 else: arr[i-zeros], arr[i] = arr[i], 0 except: return the arr.index(0)+1 is so that i can do arr[i-zeros], arr[i] = arr[i], 0 instead of arr[i-zeros], arr[i] = arr[i], arr[i-zeros] and also not need to do a else if zeros > 0 for a less python approach (they are basically the same speed) and not have a try catch this would look more like def n_run(arr): zeros: int = 1 start: int = -1 for i in range(0, len(arr)): if arr[i] == 0: start = i break if start == -1: return for i in range(start+1, len(arr)): if arr[i] == 0: zeros += 1 else: arr[i-zeros], arr[i] = arr[i], 0
I did something similar but you could save some space complexity with this def func(arr): count = 0 leng = len(arr) for i in range(leng): if(arr[i] == 0): count+=1 else: arr[i - count] = arr[i] for i in range(count): arr[leng - 1 - i] = 0 return arr
I bet there's some cleaver algorithm to do this entirely in place, so O(n) time complexity and O(1) memory complexity. I couldn't think of it off the top of my head, though.
That was my initial thought too. Instead of removing and appending, just swap the elements as you iterate. Space complexity would be O(1) it that case and time complexity would remain at O(n)
def func(array): t = [] z = array.count(0) # o(n) for e in array: e != 0 and t.append(e) return t + [0]*z "e != 0 and t.append(e)" is technically faster than if/else because branches slow down programming and short circuiting exists additionally array.count is faster than manual counting because it is a builtin method and hence handled by C, it is also an additional requirement to avoid branching
I feel like the use of short circuiting is a negligible increase in speed with modern python interpreters. I think using an if statement is just easier to read, also no "else" is needed afaik
The same can be done with list comprehension too non_zero = [i for i in array if i!=0] for i in array: if i==0: z+=1 Output = non_zero.extend(z*[0]) return(output)
You could move the array to a linked list, since that has a remove and append that is O(1). Overall that would be O(n), but I think that your solution is faster, since it requires less copying around.
@@minh-tamdoan5199 im confused, the iteration wouldn't matter if it was just using the remove method on the linkedlist though? unless you remove it from the iterator (which im not sure is a thing in python) or just remove the node directly
It's unclear whether the initial code was well-thought-out, but it didn't work as described. If we make a slight change to the problem - for each occurrence of 0, we want to remove it and append a -1 at the end - the problem can be solved with a one-line modification to the original code: def func(array): for i in array: if i == 0 : array.remove(i) array.append(-1) return array arr = [0, 0, 1] print(func(arr)) But this does not work as expected. The output produced is [0, 1, -1]
You can do this in 1 line, and avoid all the other problems with mutating iterables. ```python def shiftZero1(data: list[float]) -> list[float]: return [x for x in data if x != 0] + [0]*data.count(0) ```
I am new to python, and I got some questions while tweaking the code > Q-1 ============================================= I tried replacing ` n = 200000 ` with `n = 10000000 ` the result of ` stop-start ` is way shorter than the actual process time, why? > Q-2 ============================================= when ` n = 200000 ` I tried replacing [] with () arr = [random.randint(0, 9) for _ in range(n)] V V V V V V V V V V V V arr = (random.randint(0, 9) for _ in range(n)) The result of ` () ` is way slower than ` [] `, why?
Use two pointers, one at the start one at the end, then: while right is 0 and right > left: - move right to the left while left < right: if left is zero: swap left and right move right to the first non-zero number to the left move left to the right
We dont even have to use any extra memory. We can modify the array in-place for O(n) time complexity as well. This is what I came up with in C. /* * Takes in an array of integers and its length, and returns an array of * the same length with the same elements, but with all the 0s moved to * the end of the array. */ void int_arr_shift_0(int length, int *array) { int current_index = 0; for (int i = 0; i < length; i++) { int item = array[i]; if (item != 0) { array[current_index] = item; current_index++; } } for (int i = current_index; i < length; i++) { array[i] = 0; } }
The first approach is terrible, although it works by accident. Mutating array during iteration is a bad idea; it skips the next item after you removes the current item (this can be seen by adding a print statement to the loop). It works because it do enough time of remove/append.
When I saw your title and cover I thought you were talking about this...
I had encountered the problem you are mentioning here, around 2 years ago and it took me a month for find and remove it. I have to say it was a nightmare. now I see the code that does that I'm scared to death.
Oh. Right, that’s why it does not infinite loop at the end. If he recheck the same position then it will.
yeah i was wondering wouldent it cause an inf loop or dropped inputs.
I thought the exact same, but the video turned out different than I thought
that is also what i thought
Another easy optimization might be to populate t with zeroes. Then appending each time won't have to create another copy if overflown. It also has the added bonus that you don't have to extend with zeroes.
```
def func(array):
t=len(array)*[0]
i=0
for e in array:
if e:
t[i]=e
i+=1
return t
```
Good
unless python has some kind of optimization here len(array) * [0] would loop as populating it requires you to well loop and add each value, making it O(n²)
@@thomaseb97thats still O(n) since length is
res = 0
For _ in list:
res += 1
This is slower in Python. While it is good practice in all other languages to allocate the correct amount of memory for the array. In Python the first line "t = len(array)*[0]" takes O(n), all the way to n. Then the for loop also goes all the way to O(n). Making the final time O(2n).
Compared to b001's solution: There the total is O(n + z) where z is the number of zeros in array and z < n. In the worst case z == n, so it goes to O(2n), but shawon's solution is O(2n) every time. When z
@@Fishpizza1212
"""
def func(array):
t=len(array)*[0]
You could use a list comprehension in the form of a filter
t = [x for x in array if x != 0]
The complexity would be the same but a list comprehension would be computationally faster than the call to append.
The counter can simply be replaced by the difference in length between t and the original array.
For counting zeroes you can use array.count(0).
@@robertredziak6461True... Not sure what would be more optimum but definitely correct
after trying a few things, ive found this to be the fastest solution. It takes 0.04s on average for an array 1m integers long, compared to the video's solution that takes about 0.05s for me.
This, IMO, is the best and most Python solution.
This seems like the best solution in since list comprehension goes brrr
b001, your production quality is always fantastic. This is my favourite video of yours so far. I like the flow of the different steps -- hearing your plan of attack, watching your solution, then exploring an optimisation. You teach so much in such a short amount of time. Cheers.
Thanks! Really glad you enjoyed!!
This method does it in place (no new array):
def func(a):
i = 0
l=len(a)
while i
I was just wondering if there'd be a way to do this! I'm guessing this'd also be super fast in C, since accessing an array in C is just a single pointer dereference, where as shifting memory on the stack or (even worse) allocating / deallocating it on the heap is relatively slow.
We sacrificed memory for time improvement here. You can achieve a huge improvement without sacrificing memory by iterating by index and using the .pop method.
I would say that it's a coincedence that first code is working at all. When you remove an element from the list you are iterating over, result is rather unpredictable and depends on current implementation of the list (and could change between version). If you alter the task slightly and ask to just remove all the zeroes instead of moving them to the end and try to solve it by the same code with "array.append(0)" line commented, it'won't be just slow, **it would break the data** (currently).
So, algorithm complexity is the least important problem with such approach, it has a huge potential of being buggy.
For this specific task you could do it in linear time inline with an iterator and a counter (as was already mentioned in comments), or with something like `return (res := [x for x in array if x != 0]) + [0] * (len(array) - len(res))` (or spread it over 3 lines if you are afraid of walrus :-) )
Additionally, there is a common method for tasks like that, when you need a complex rules of sorting:
` return sorted(array, key=lambda x: (False, x) if x != 0 else (True, 0))`
Basically, usage of tuples for key function in sort allows you to specify a hierarchy of elements and give a special treatment for zeroes in this case. Complexity is nlogn, but for not so big lists it shold be fine and universal solution.
You can also solve this problem using the two pointer approach:
def func(arr: list[int]) -> list[int]:
try:
lt = arr.index(0)
except ValueError:
return arr
rt = lt + 1
while rt < len(arr):
if arr[rt] != 0:
arr[lt] = arr[rt]
lt += 1
rt += 1
while lt < len(arr):
arr[lt] = 0
lt += 1
return arr
The advantage of this approach is that that you’re not creating a new array, so memory is constant.
yikes...might as well just use sort
@@hallooww sorting is slower. Albeit not much slower in Python specifically, given sorting is built-in and, like most built-in functions in Python, is mostly written in C. But in general a quick sort is O(n log n), whereas this algorithm is O(n).
@@AWriterWanderingconstant * n, practictally log is incredibly minimal. your code is quite literally goofy my brother, take a step back
@@hallooww you think a bog standard two pointer algorithm is goofy? Try looking into the TimSort algorithm that Python actually uses under the hood. 😂
@AWriterWandering, from the stable sort of timsort which handles false boolean values by placing them at the end, particularly benefiting from Python's binary optimizations, what are you even arguing? asserting that a try block with index() is optimal shows your incompetence, especially considering the comparable efficiency of if 0 in arr (both O(n) operations), along with the additional overhead introduced by the try block.
Absolutely proud of myself for figuring out the more efficient way of doing it as soon as I saw the first method. No, I won't accept being told how simple the problem was-
Same here lmaoo
Ikr, although my reason for doing it that was was a fear of skipping over any values in the for loop, a fear that has stuck with me since I learnt list comprehension instead of using the index
You could also keep track of the last element that is not a zero, loop through the list and when encountering a zero swap with that element
I finally get Big O notation, thanks b001!
This can also be done on the same reserved list without duplicating memory. You just have to maintain a couple of position integers. Loop all the list through the read position. When a zero is encountered increment the read position. When a non zero is encountered copy the value from the read position to the write position and incremento both. To finish up fill from write+1 to the end with zeroes
An *excellent* solution. Saves memory and CPU time.
You need to be careful about whether to fill, and how much. Here's an example of how to avoid unwanted filling:
def sortem(nums):
if len(nums) < 1 or not isinstance(nums[0], int):
return
wptr = 0
for rptr in range(len(nums)):
if nums[rptr] == 0:
continue
nums[wptr] = nums[rptr]
wptr += 1
if wptr and wptr < len(nums):
# Only fill if we found both zeros and non-zeros
for i in range(wptr,len(nums)):
nums[wptr] = 0
return
You got my sub for this video man, i enjoy every moment of it 🎉. Cheers
You can simply swap first encountered non-zero with the first encountered zero, which is even more optimal, as it doesn't use external space. I am not using python at all, so it can be probably written more "pythonically", but this is the basic idea:
def shift_zeros(array):
last = 0
for i, num in enumerate(array):
if num:
array[i], array[last] = array[last], array[i]
last += 1
return array
Nice solution!
We had a discussion in the discord and I think we finalized a pretty elegant solution:
def shift_zeros(array):
return [*filter(None, array] + [0]*array.count(0)
@@b001SyntaxError: closing parenthesis ']' does not match opening parenthesis '('
@@RandomGeometryDashStuff return [*filter(None, array)] + [0]*array.count(0) he just forgot to write a bracket, of the filter function, but the idea is good
yeah this was my first though as well, although you can probably do better with built-ins since those are in c instead of python, but that's a bit of a cheat code :)
@@b001 I got this version to perform better by ~15%: lambda array: [*filter(None, array), *(array.count(0)*[0])]
This is probably not worth the degredation in readibility though
We can also slove using 2pointers approach
With TC:O(n) and SC:O(1)
It is the most optimal approach.
Nope, that depends on the language.
ruclips.net/video/kXuPLvMQl44/видео.html&lc=UgzPO-ZVO-XJUzgDmxN4AaABAg
You can also use the divide and conquer technique, though it wouldn't be as efficient, but it will save you the space complexity. First split the array until you reach a base case of 1 or 2 elements, and swap the first element with the second if the first is a zero, else do nothing - then when merging the two arrays, you already have them with ending 0s, so you simply can combine them in a similar manner to merge sort. Merging two arrays is O(n), and splitting will be O(logn), so the time complexity is O(nlogn). But because you can do this in place, the space complexity is O(1).
It's a bit unecessary to create a whole new array, since it can become costly for large n. Instead you could iterate over the array and keep track of the leading zero. As soon as you find an element which is non-zero, you simply swap the zero and the element and increment the "leading zero index" by one. This solution will have O(n) timecomplexity and O(1) space complexity.
This solution sounds interesting to me, but I’m not sure if I understand completely. With “leading zero” do you mean the first zero you encounter in the list at that point in time? Because it sounds like this solution would slot a lot of numbers in slots previously occupied by zeros which could be randomly distributed trough the list and thus these numbers would be randomly distributed as well. Thus creating a very different list of numbers and not fulfilling the promise of only moving the zeros to the end. Please do correct me if I misunderstood :)
@helboy1111 yes exactly, with leading zero I mean the first zero encountered in the list. Imagine the following example:
{ 1, 0, 0, 2, 0, 3 }
We iterate over the list above with a variable X as our index. We find the first zero at X = 1 so we store that in a variable Y. If we move forward through the list until we find the 2 when X = 3 we can safely swap the values at index X and Y to produce the following intermediate list:
{ 1, 2, 0, 0, 0, 3 }
As you can see, we have not changed the relative order of the non-zero numbers. Now we simply increment Y because we know that the following number MUST be a zero (or outside the list).
This is so because we swap as soon as we find the first non-zero value and even if it was located at the index immediately after Y (that is Y+1) then we would have just moved a zero to that position!
After performing the swap we can continue iterating over the list until we reach the end, repeating the swap-and-increment procedure for every non-zero value found.
Hope this clears it up :)
@@BeholdTheDevil Ah thanks a lot, this clears up my confusion completely. It wasn't clear to me before that you would only take non-zero elements after the leading zero. Which makes sense in hindsight, considering the well-named "leading zero".
Good solution. However, consider [1,0,2,3,4], in which the 2,3 will be updated to 0 only to be overwritten again. Since there will a lot more non-zeroes, this becomes quite inefficient. Instead assume the swapped non-zero becomes 0 and then after the last "swap", update to 0 the elements after the leading zero index. So worst case each element is updated once.
@@badhombre4942 I suppose that is a valid point. There is really no need to write the zeroes before the end. Although I doubt this would have any major performance penalty, as a register swap can be done in a single cycle CPU instruction, it would be interesting to see if it made a difference.
I used the same idea, but with list comprehension and the count method
def func(array):
t = [i for i in array if i != 0]
z = array.count(0)
t.extend(z * [0])
return t
my solution is the same comprehension but to get z i use len(array) - len(t) to not have to incur another O(n) cost of .count
@@DDvargas123i have same solution man 👍🏻
@@DDvargas123len is O(n) so that accomplishes little
@@tylerharmon5028 I don’t think that is correct for a list.
@@TehKarmalizer Actually you're right. Python stores the length of a list as metadata with the list and updates it when the list is modified, so __len__() call is O(1). My bad.
def func1(array):
temp = list(filter(lambda e: e != 0, array))
return temp + [0 for _ in range(n - len(temp))]
def main(array: list) -> list[int]:
result = [element for element in array if element]
return result + [0] * (len(array) - len(result))
great work man.. very helpful for me as a beginner. keep it up. really appreciate it.
I though about the second solution instantly, but for a different reason, I would never append or remove elements from an array while iterating thru it, creating a new array is safer...
Good Approach
def func(array):
for i, num in enumerate(sorted(array)):
if num > 0:
return array[i:]
Sorted function actually compression O(n log n)
don't use time.time to measure performance, use from time import perf_counter instead
Any opportunity not to use loops should be utilized . A simple list comprehension over the list if != 0, inserted at the beginning if a zero array or padded with zeros.
I love optimization. I do it more with spark and relational databases, but the value one gets out of optimizations is way more than compound interest.
This random video might honestly help me with item sorting in my game, since the current way I do it is by not doing it at all.
@@0LoneTech there actually is an array sort function in game maker but I haven’t red about it yet. I will consider it though.
@@0LoneTech the way I’m doing the inventory system in my game has two parts, the items and the non-item slots. I do use this method to update the inventory every frame so that it returns whatever items to the top that I may have accidentally misplaced using my placer variable. I believe arrays_sort() requires a function to work properly which is why I haven’t really used it yet as I’m still learning what that would even mean. So yes, I acknowledge the difference, but I think I just used the wrong terminology to describe my inventory system.
Good example, well done
My immediate thought was to create a list with conditional slicing to create two lists with the integers and zeros, then concatenate.
list2 = [ x for x in list1 if x != 0 ]
list2 += [0] * (len(list1) - len(list2))
simple, short and pythonic
My personal intuition on how to do this in-place in O(n) time is to iterate forward in the array until a zero is reached, then iterating backwards until a nonzero is reached, switching the values, continuing to repeat until the two indices meet in the middle.
If I understand your solution correctly, I think it does not work. Take 1,0,2,3 as the input, you solution will produce 1,3,2,0 but it is supposed to be 1,2,3,0
@re-lax3580 yeah, I didn't think this through very well last night. It isn't stable with respect to non-zero elements.
Your final solution use extra memory (temporary array of n elements). I have an idea how to improve first method. Instead of appending and removing elements from array, just replace items instead. Create 2 pointers, first is a start of an array, second is last element. Then go through array using 1st pointer. If number is not 0, increment 1st pointer. Else swap that zero with 2nd pointer and subtract 1 from 2nd pointer. Continue untill 2 pointers point on the same element.
The problem is that the non-zero elements would be out of order at the end. If that weren't a requirement then this would be a good approach.
I am at 2:22 and I want to see if I can figure it out myself.
At first, I would create a new list and a "zero-counter". When looping through the list, if the number is a non-zero digit (1-9), I append it to the new list. Else, if it's 0, I increase the zero counter by 1. At the end of the loop, once all positive numbers have been placed in the list, I make a for loop with a range(zero_counter), which will append the same amount of zeroes to the final list as the amount there were on the original list. Now return that list.
3:04, it was exactly what I thought.
Need more of these ma man
It works but you would need 2x the memory. One approach would keep a record of zero's indexes of the list if you expect it to have fewer zeros then items, then you can shift everything after.
you can use generators too that's a great middle term
In put of simple termes this could be used to other codes
If your code has to go around the road to go to it's destination it will take longer but if it takes longer to think and pick a shorter way it will go to it's destination faster
So if anyone's code is slow maybe you can try to imagine it differently on how it could go faster like he did right here
My first instinct was merely to make 2 empty arrays, append to array 1 if != 0, else append to array 2, then concatenate two lists outside loop, and return.
Thanks for this great video❤
def swap(array, i, j):
array[i], array[j] = array[j], array[i]
def func(array):
i = 0
for j in range(len(array)):
if array[j] != 0:
swap(array, i, j)
i += 1
return array
Excellent explanation...
what theme r u using?
.
my first approach was close to your second aka making a temp array and a zero counter. however instead of multiplying zeros to the end using extend i just made a nother for loop and apanded the zeros to the end.
Python uses lists not arrays, so why would it shift all of the elements forward by 1 instead of doing a normal linked list deletion?
@@0LoneTech so does python use amortized array growth or something then if you add more items to the list?
Rather than creating a loop, I would create a list (temp) with list comprehension:
temp = [i in array if i != 0]
Or transform it into a set and get the difference
temp = list(set(array) - {0}) # only works if the original array does not have replicates
And comput z which is the difference between the length of the two lists:
z = len(array) - len(temp)
What VS Code theme is that?
best optimization , user 2 pointer algorithm
Technically O(2N + C), there are more operations that are happening so we just go with C and it's so small that it doesn't even matter.
I would like to point out your use of space that wasn't covered. I really do think you could do an in place change to the list without having to sacrifice additional space.
Space appears to be O(2N) as well. If this where billions of integers we would have to allocate twice the size, arguably it's fine, but in a MAANGT interview I can see a hiring manager getting amped about that.
I'm like 90% sure that that question has the constraint that the original array should be modified and you can't use extra memory
yo bool what is your vscode theme??
i love it i wanna try it out
def func(array):
x = list(filter(None, array))
y = list(filter(lambda s: s == 0, array))
return x + y
i think this solution also can pretend to be good
Do you do code analysis if someone submits you their code?
Love this type of video.
Also, do you know anyway to remove titlebar in tkinter effectively, pls make a video :3
sorted(a, key=operator.not_)
You can do this in-place with O(n) by keeping track of the number of zeroes encountered so far and moving back nonzero elements that number back
UPDATE #2:
So I've found an even faster method. On my PC this method is faster than the list comprehension method I've tested even though the doc's indicate they should be equivalent:
def test_filter_method(input):
filtered = list(filter(None, input))
return filtered + ([0] * (len(input) - len(filtered)))
This seems to be about the limit you can go with speed on this problem and I'm not sure I'm going to find a faster way.
UPDATE:
This really piqued my curiosity so I decided to time a few methods and come to some interesting conclusions.
The first method I tried was to see if the sort function could do this, and yes it can. Using a lambda like here:
def test_lambda(input):
return sorted(input, key=lambda x: 1 if x == 0 else 0)
def test_lambda_in_place(input):
input.sort(key=lambda x: 1 if x == 0 else 0)
return input
both methods are slightly slower than the list comprehension method I mention below. But if you want to keep your space complexity lower it is very good and I wouldn't blink at using this.
I did find a faster way though. After reading through some of the docs you can provide a constructor to the key argument in sort and, exploiting some of the nuances of the problem at hand, you can do this:
def test_constructor(input):
return sorted(input, key=bool, reverse=True)
def test_constructor_in_place(input):
input.sort(key=bool, reverse=True)
return input
Both of which take nearly the same test time of my original list comprehension method, if not lower in some cases. Incredible really. So the take away, if you can do use pythons constructors and basic types, and sorting is fast very very fast.
----- Old Post ----
The way i would do it is using list comprehension a list multiplication:
def test_list_comprehension(input):
filtered = [x for x in input if x != 0]
return filtered + ([0] * (len(input) - len(filtered)))
In general list comprehension is very fast especially for such simple filters and list multiplication is extremely fast so I would expect this to be near optimal.
For those that also are talking about space complexity you can always keep the time complexity below O(2n) with a constant space complexity by doing the following:
def test_naive_in_place(input):
ins = 0
for i in range(len(input)):
if input[i] != 0:
input[ins] = input[i]
ins += 1
for i in range(ins, len(input)):
input[i] = 0
return input
This approach will be considerably slower however and should be avoided unless you're dealing with HUGE lists. Even then an iterable or another solution may be better.
a stupid but easy way is to make a new array, loop through the first array and just insert all the regular integers and then once that's done, fill the rest of the list with zeros (if they aren't already initialized to zeros anyway), then if it NEEDS to be in the first array, just write each value of the new array to the original.
he did that at the end of the video...
if this was a question during an interview, the answer most likely would not be consider complete, as most likely, the interviewer would ask you to rewrite the program as to Not use an additional memory O(n) in this case, but manipulate the existing array.
Which type font theme color are yo using in your vs code.😅
Yes this is my immediate solution too, but be mindful of what it's doing,. you are trading time complexity for space complexity, you are basically doubling the allocation in memory since you are creating a new array of N at the end.
Thanks! The new way is what I would have done (🏆 for me!)
Use list comprehension, populate the temp array with zeros and dont check the last element of the array.
which font are you using
I tried writing an in place solution:
def run(arr):
try:
zeros: int = 1
for i in range(arr.index(0)+1, len(arr)):
if arr[i] == 0:
zeros += 1
else:
arr[i-zeros], arr[i] = arr[i], 0
except:
return
the arr.index(0)+1 is so that i can do arr[i-zeros], arr[i] = arr[i], 0 instead of arr[i-zeros], arr[i] = arr[i], arr[i-zeros]
and also not need to do a else if zeros > 0
for a less python approach (they are basically the same speed) and not have a try catch this would look more like
def n_run(arr):
zeros: int = 1
start: int = -1
for i in range(0, len(arr)):
if arr[i] == 0:
start = i
break
if start == -1:
return
for i in range(start+1, len(arr)):
if arr[i] == 0:
zeros += 1
else:
arr[i-zeros], arr[i] = arr[i], 0
I did something similar but you could save some space complexity with this
def func(arr):
count = 0
leng = len(arr)
for i in range(leng):
if(arr[i] == 0):
count+=1
else:
arr[i - count] = arr[i]
for i in range(count):
arr[leng - 1 - i] = 0
return arr
I bet there's some cleaver algorithm to do this entirely in place, so O(n) time complexity and O(1) memory complexity. I couldn't think of it off the top of my head, though.
Can someone give me a link for the timeing part ?
I dont understand O(n) thing
You can do it in place too, right? Keep two indexes and move the items over
That was my initial thought too. Instead of removing and appending, just swap the elements as you iterate. Space complexity would be O(1) it that case and time complexity would remain at O(n)
def func(array):
t = []
z = array.count(0) # o(n)
for e in array:
e != 0 and t.append(e)
return t + [0]*z
"e != 0 and t.append(e)" is technically faster than if/else because branches slow down programming and short circuiting exists
additionally array.count is faster than manual counting because it is a builtin method and hence handled by C, it is also an additional requirement to avoid branching
I feel like the use of short circuiting is a negligible increase in speed with modern python interpreters. I think using an if statement is just easier to read, also no "else" is needed afaik
Use map function and the performance will be even more improved (e^-5)
Replace func(arr) with x=map(func, arr)
The same can be done with list comprehension too
non_zero = [i for i in array if i!=0]
for i in array:
if i==0:
z+=1
Output = non_zero.extend(z*[0])
return(output)
@epsi Thanks mate
This warlus operator is cool
you dont need to do the second loop here, you could simply do len(array) - len(non_zero) and that would be the zeroes you skipped
@@thomaseb97 Thanks mate
@@thomaseb97how about array.count(0)?
how about using deques?
rotate through deque -> O(n)
if 0
.pop -> O(1)
append to new deque/list -> O(1)
return deque+new deque
Thank you.
You could move the array to a linked list, since that has a remove and append that is O(1). Overall that would be O(n), but I think that your solution is faster, since it requires less copying around.
isn't remove by index on linkedlists O(n), since you have to iterate from the head to get to the corresponding node?
since we are iterating through the linked list anyway, it’s O(1).
@@minh-tamdoan5199 im confused, the iteration wouldn't matter if it was just using the remove method on the linkedlist though? unless you remove it from the iterator (which im not sure is a thing in python) or just remove the node directly
i also specifically mentioned removed by index, im pretty sure thta just starts iterating separately from the iteration you're already doing
What vscode theme are you using?
It's unclear whether the initial code was well-thought-out, but it didn't work as described. If we make a slight change to the problem - for each occurrence of 0, we want to remove it and append a -1 at the end - the problem can be solved with a one-line modification to the original code:
def func(array):
for i in array:
if i == 0 :
array.remove(i)
array.append(-1)
return array
arr = [0, 0, 1]
print(func(arr))
But this does not work as expected. The output produced is [0, 1, -1]
or then:
def func(arr):
count = arr.count(0)
for i in range(count):
arr.remove(0)
arr.extend([0] * count)
return arr
my first thought:
def func(array):
sec = list(filter(lambda x: x != 0, array))
sec.extend([0 for i in range(len(array)-len(sec))])
return sec
absolutly blilliant
def func(array):
sa = ','.join(map(str,array))
b = sa.replace("0,","").split(",")
b += array.count(0) * [0]
return b
You can do this in 1 line, and avoid all the other problems with mutating iterables.
```python
def shiftZero1(data: list[float]) -> list[float]:
return [x for x in data if x != 0] + [0]*data.count(0)
```
zeros = sum(1 for x in array if x == 0)
array = filter(lambda x: x != 0, array)
array += [0 for _ in range(zeros)]
does any one know about the font?
The name of the font?
Just going from the thumb nail here:
def shift_zeros(arr:list[int])->list[int]:
return [a for a in arr if a!=0]+([0]*arr.count(0))
this is different
def func(array):
temp = [x for x in array if x != 0]
return temp.extend((len(array)-len(temp)) * [0])
great solution
def shift_zero(l):
list_nz = [i for i in l if i]
return list_nz+(len(l)-len(list_nz))*[0]
Nice solution! Just compared it with mine and yours beats it every time. Yours is cleaner too!
@@b001 Thanks man, I like your "problem" videos, it's good to sharpen those problem solving skills
def moveZeroes(nums):
nonzero = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[i] , nums[nonzero] = nums[nonzero], nums[i]
nonzero+=1
return nums
pretty straighforward and constant memory
Generate random list with random numbers until it is correct
return [x for x in list if x] + [x for x in list if not x]
I am new to python, and I got some questions while tweaking the code
> Q-1 =============================================
I tried replacing
` n = 200000 `
with
`n = 10000000 `
the result of ` stop-start ` is way shorter than the actual process time, why?
> Q-2 =============================================
when ` n = 200000 `
I tried replacing [] with ()
arr = [random.randint(0, 9) for _ in range(n)]
V V V V V V V V V V V V
arr = (random.randint(0, 9) for _ in range(n))
The result of ` () ` is way slower than ` [] `, why?
Q1: `arr = [random.randint(0, 9) for _ in range(n)]` need some time to initialize
what if we filter the array by removing all the 0 elems and compare the length of both arrays, and just append 0 * length difference
Now you have 2n space complexity
Ya counting the 0’s was the first thing
Why not .index[]0
list = [1, 2, 0, 3, 0, 4, 5]
shifted_zeroes = [elem for elem in list if elem != 0] + [elem for elem in list if elem == 0]
Use two pointers, one at the start one at the end, then:
while right is 0 and right > left:
- move right to the left
while left < right:
if left is zero:
swap left and right
move right to the first non-zero number to the left
move left to the right
We dont even have to use any extra memory. We can modify the array in-place for O(n) time complexity as well. This is what I came up with in C.
/*
* Takes in an array of integers and its length, and returns an array of
* the same length with the same elements, but with all the 0s moved to
* the end of the array.
*/
void int_arr_shift_0(int length, int *array) {
int current_index = 0;
for (int i = 0; i < length; i++) {
int item = array[i];
if (item != 0) {
array[current_index] = item;
current_index++;
}
}
for (int i = current_index; i < length; i++) {
array[i] = 0;
}
}
why is the thumbnail hungarian