CODEWITHSUNDEEP
pythonarraysindexingin-place
Jane Sully
Jane Sully

Reputation: 3337

In-place modification of array in python

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

Upvotes: 3

Views: 7657

Answers (1)

bunbun
bunbun

Reputation: 2676

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

enter image description here

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.

Upvotes: 1

Related Questions