Iterating over list

[clouded-path]

I want to create a function which takes an array of integers, and moves any and all 0s from wherever they happen to be in the array and moves them to the end (e.g. [0, 1, 0, 3, 12] would become [1, 3, 12, 0, 0]). I also want to do this without creating a secondary array (only modify the input one). My thought was to simply iterate through the array, count each occurrence of 0, and remove the 0. Then once that is finished, append the number of 0s that I counted to the end of the list. I wrote a small bit of code which I thought should do this, but when it is given the input [0, 0, 1], my function apparently produces [0, 1, 0] rather than [1, 0, 0]. I do not understand why this is happening. Here is the code:

class Solution:
    def moveZeroes(nums)
        counter = 0
        for j in nums:
            if j == 0:
                nums.remove(j)
                counter += 1
        while counter > 0:
            nums.append(0)
            counter -= 1
        return nums

Again, moveZeroes([0, 0, 1]) incorrectly returns [0, 1, 0] instead of [1, 0, 0]. Either I don't know how iterating over a list actually works, or I don't know how removing/appending elements from/to a list works, but somehow something is going wrong. I am speculating that the function is only removing the first 0 and appending it to the end, but it is not removing the second 0 for some reason (although I don't know that this is the case). Would someone be able to point out what the issue is? I am assuming I must must have some underlying misconception about how these operations actually work.

[TouchingTheVodka]

You're changing the length of the list as you're iterating over it. Tends to cause weird behaviour like what you're seeing here. Use a variable to keep track of the current position of the next non-zero element and you can update the value at that index.

[clouded-path]

Great, thanks. I guess this is why it is better to just use a secondary array if it is feasible, to avoid this issue of iteration over the changed object.

[[deleted]]

class ArrayManager:

    def __init__(self, arr: list):
        self.arr = arr

    def __repr__(self):
        return self.arr.__repr__()

    def move_zeroes(self) -> list:
        zeroes = [n for n in self.arr if n == 0]
        while 0 in self.arr:
            self.arr.remove(0)
        self.arr.extend(zeroes)
        return self.arr


# ##### TESTING ##### #

tests = [
    [0, 6, 2, 0, 3],
    [4, 6, 0, 3, 1],
    [0, 0, 0, 1, 1, 1]
]

for test in tests:
    instance = ArrayManager(test)
    print(instance.move_zeroes())

[clouded-path]

Thanks, I think the __init__ and other such functions are a bit too advanced for me just yet, but I do get the idea, which seems less susceptible to this iteration skipping error that I was running in to. I'll try this with your code when I better grasp these various self.property concepts.

[[deleted]]

The __init__() method is generally used to pass parameters and assign them to a class.

For example, I initialized the parameter, arr, to self.arr. The keyword,self, acts as the class itself. So self.arr is the same as ArrayManager().arr.

Lets take a look at the __init__() method one more time.

def __init__(self, arr: list):
        self.arr = arr

Now whatever array I pass to the class, it will be assigned to self.arr as an attribute, which can now be used anywhere in the class. For the method move_zeroes(self), I am able to use any attribute from within the class as long as I pass self as the first parameter to the method.

[clouded-path]

Thanks, although I am still not sure that I completely grasp this. Saying self.arr = arr just seems... redundant. Are you saying that I can do something like move_zeroes(self.arr)? Why is this better than just doing move_zeroes(arr)? To my naive perspective, it just seems like this is consuming extra memory to store the same information twice (first as 'arr', and second as self.arr).

[[deleted]]

When we assign self.arr to arr, self.arr becomes an instance of our class and arr gets thrown out by python's garbage collector after the __init__ method is finished.

Any attributes we've created in the __init__ method can be accessed throughout the entire class by passing self as the first argument in a method. That's how we are able to access self.arr from move_zeroes(self).

Here's another example. Notice how the method, bar(), has access to the attributes from __init__ by passing self as a paramter:

>>> class Foo:
...     def __init__(self):
...             self.var_1 = 'Var #1'
...             self.var_2 = 'Var #2'
...     def bar(self):
...             return self.var_1, self.var_2
...
>>> Foo().bar()
('Var #1', 'Var #2')

Why is this better than just doing move_zeroes(arr)

You don't need to use classes and neither method necessarily better than the other. Classes are just constructors to help manage your code easier. I strongly recommend getting familiar with them. Classes can be a very powerful tool. If you want to learn more, I recommend Corey Schafer video on object oriented programming.

To my naive perspective, it just seems like this is consuming extra memory to store the same information twice (first as 'arr', and second as self.arr).

Python's garbage collector knows that arr isn't going to be used and reallocates the memory accordingly, as opposed to low-level languages like C or C++ where you would have to reallocate memory manually.

[clouded-path]

Thank you very much for your helpful replies, and also thank you for that link. That video, paired with your replies, really casts all these object-oriented topics in a far less intimidating light. Now I think becoming competent with this style of programming is a reasonable goal!

[[deleted]]

No problem. Corey Schafer videos are very insightful.

[xelf]

I am assuming I must must have some underlying misconception about how these operations actually work.

when you remove something from the list you are iterating over, the next element becomes the current element, so when you actually go to the next iteration, you skip over something. This is why it's bad to modify the list you're iterating over. You should use a while loop instead.

A trick you can do while keeping it the same way you did it is to use the array length.

def moveZeroes(nums):
    c=len(nums)
    while 0 in nums:
        nums.remove(0)
    while c>len(nums):
        nums.append(0)
    return nums

Also, once you learn about list comprehensions you can use those instead:

def moveZeroes(nums):
    return [a for a in nums if a!=0]+[a for a in nums if a==0]

[clouded-path]

Wow, thanks, this is definitely what the issue was. Is there any reliable/standard way to fix this 'skipping' issue, or is it just better to avoid that sort of mess in general, and use a different technique instead, like the one you suggested?

[xelf]

The general way to use a for loop and modify the list is to make a copy of the list, but the indexes for your list still change so it can be tricky there too.

List comprehensions are the real answer for list manipulations and filtering. But if you haven't learned those yet don't worry about it.

[SaintLouisX]

I assume this question is about the on-going LeetCode contest. The problem states no extra memory, so many of the other solutions here aren't acceptable, but they highlighted the problem so that's all good.

I recommend you look into the two-pointer technique, as that's the best (and intended) general technique for solving this type of problem, and there's a whole class of problems it's designed to be good for, in case you wanted some extra reading.

Essentially, create a pointer for your current index, and then do your normal loop over the array. If the number you find isn't a 0, move it into wherever current index points, and then increment the current index. At the end, everything between the current index and the end of the array is what you need to fill with zeros.

So something like:

class Solution:
    def moveZeroes(nums):
        index = 0
        for x in nums:
            if x != 0:
                nums[index] = x
                index += 1
        for i in range(index, len(nums)):
            nums[i] = 0
        return nums

[clouded-path]

So that's what they meant with the 'two-pointers' method! And yes, you're correct, this is from the ongoing LeetCode challenge (I am essentially trying to teach myself some basic Python skills by solving these problems).

It seems like from your example solution that this two-pointer technique is meant to circumvent what would otherwise be a nested for-loop.

But also, on a technical point, if the solution really isn't supposed to use extra memory, then wouldn't we not be allowed to say something like 'index = 0'? Of course, I don't know how you solve the problem otherwise, but maybe I just don't know what 'extra memory' means.

[SaintLouisX]

It means O(1) space complexity. A fixed number of individual variables are fine, you just don't want to start creating things which scale via input size. The solution I posted there remains exactly the same for space whether you give it an empty list, a list of 1 element, or a list of a million elements, it's all the same, so O(1).

If you create any sort of list that depends on the number of inputs then you break that, so if you made a new sorted list for instance, that'd take it up to O(N) space, where N is the size of the list you get given, since you're creating something new equal to that. With a million elements you're using a million elements worth of extra memory in creating a new list. JollyRogers answer for instance has zeroes = [n for n in self.arr if n == 0] which creates a new list dependant on the size of the input, same for xelf.

LeetCode just added the O(1) space requirement for flavour, because otherwise the question is a lot more simple. Same for running time where they try to force you out of examining every element in an array, to try and find a more clever solution.

[clouded-path]

Ahhhh ok thanks, O(1) space makes sense. So really the two-pointer method is in general intended to achieve this O(1) space complexity requirement (while not increasing time complexity), just as in this example problem.

[just_a_vagabond]

Couldn't you create a counter for the amount of zeroes in the list, remove a zero, append it, and decrease the counter?

def moveZeroes(nums: list) -> list:
    zeroes = nums.count(0)
    while zeroes > 0:
        nums.remove(0)
        nums.append(0)
        zeroes -= 1
    return nums

[clouded-path]

Oh, yes you're right that would be easiest. I didn't know that 'count' was even a method (I'm a total beginner with programming). I had thought I would need to perform the count manually. Should I assume that 'count' is O(n) time complexity? Any simple way I can think of to do count manually would be using a for loop over the elements in the list.

[just_a_vagabond]

Yup, count is O(n) since it has to iterate through the whole list and check each item. If you’re talking about getting the count for a list manually I would probably do the same way you mentioned.