In-place modification of array in python

Question

I found this question that asks for in-place modification of an array, so that all zeros are moved the end of the array and the remaining order of non-zero elements is maintained. In-place, according to the problem statement, means without making a copy of the original array. (This is taken from Leetcode and can be found as #283, Move Zeroes)

An example input and output would be, [0,1,0,13,12] becomes [1,13,12,0,0]. One simple solution I saw is:

for num in nums:
    if num == 0:
        nums.remove(num)
        nums.append(0)

The solution is clear and easy to follow, so I get that it is doing what it is supposed to.

However, I am not fully clear/sold on the in-place part, because I am not sure how remove works in the background. Does remove internally make a copy of the array to remove the specified element - how does it work? Using this notion of "in-place", is my initial solution below considered in-place (since it does not make any copies of nums, but rather modifies the original version of nums)?

indices = []
for en, num in enumerate(nums): # get the index of all elements that are 0
    if num == 0:
        indices.append(en)

for en, i in enumerate(indices): 
    new_i = i-en # use the index, accounting for the change in length of the array from removing zeros
    nums = nums[:new_i] + nums[new_i+1:] # remove the zero element
nums = nums + [0] * len(indices) # add back the appropriate number of zeros at the end

Okay, good to know. Thanks for the tip. How would you do it instead? — Jane Sully
– Jane Sully, Commented Sep 15, 2018 at 14:30
Make a copy and iterate though it: for num in nums[:]:, then you're safe to modify the original list. — iBug
– iBug, Commented Sep 15, 2018 at 14:31
I think I mention this above (but it should have been explicitly stated), but the original problem states to "move all 0's to the end of it while maintaining the relative order of the non-zero elements and doing so in-place without making a copy of the array". — Jane Sully
– Jane Sully, Commented Sep 15, 2018 at 14:35
The you'd better do for i in range(len(nums)) and access the array by indices. — iBug
– iBug, Commented Sep 15, 2018 at 14:39

bunbun · Accepted Answer · 2018-09-15 14:40:28Z

Does remove internally make a copy of the array to remove the specified element?

No

How does it work?

From the python source code for lists, remove() calls listremove():

listremove(PyListObject *self, PyObject *v)
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
        if (cmp > 0) {
            if (list_ass_slice(self, i, i+1, (PyObject *)NULL) == 0)
                Py_RETURN_NONE;
            return NULL;
        }
        else if (cmp < 0)
            return NULL;
    }
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

Python slices the list at the index of the item to be removed. I found a better description of the remove function here:

arguments: list object, element to remove
returns none if OK, null if not
listremove:
    loop through each list element:
        if correct element:
            slice list between element's slot and element's slot + 1
            return none
    return null

With your notion of "in-place", I would say it is fairly in place, and works for your specific situation. But someone has already made a good point about taking note not to modify a list while iterating through it.

Collectives™ on Stack Overflow

In-place modification of array in python

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related