In-place solution

Python Help
1

A simple coding question. I was wondering if my solution is “in-place”?

Move Zeroes

Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]

Example 2:

Input: nums = [0] Output: [0]

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums[:] =  [x for x in nums if x != 0] + [x for x in nums if x == 0]

I understand that the class does nothing and is redundant. I just followed the template of the website.

Is my solution “in-place”? If not, does there any simple modification work?

2

EDIT: following does not address OP problem as I misread it. It sorts instead of keeping original order of non-zero integers

Python lists have built-in in-place .sort method. You just need to provide key function to put zeros at the end. This can be done by taking advantage how Python sorts tuples (or any other sequences):

nums = [0,1,0,3,12]

def sort_with_priority(list_):
    def keyfunc(num):
        if num == 0:
            return (1, num)
        return (0, num)
    list_.sort(key=keyfunc)

sort_with_priority(nums)

print(nums)

# -> [1, 3, 12, 0, 0]
3

It is in-place in the sense that the final result is in the original object. …but during the process of creating the result you are creating a new list of the same length. Only after that you assign its items to the original list. In real tasks this could be a problem when the list is huge and occupies a lot of memory.

To perform the task without creating the new lists you have to remove the zero elements and append them to the end of the list.

Below, in the linked documentation there are operations applicable to mutable sequences. list is a specific type of mutable sequences. At least two of the operations are suitable to accomplish the task. Try to figure it out.

@aivarpaalberg your code is a good example how to use a special key function for sorting but it does not keep the non-zero elements order how it is required in the exercise. It is just a coincidence that it works with their example.

4

Mea culpa - this is my mistake. I somehow read that it must be sorted. I reality the objective was to keep the original order of non-zero items and indeed my code will not deliver desired result.

5

Heh, well that depends on what you mean by “in-place”. There is a weak meaning and a strong meaning.

The weak meaning is that you don’t return a new list, but modify the existing list. You have certainly done that, so in the weak sense, you have modified the list in-place.

The strong meaning is that you don’t use any extra storage, but do all the work directly in the existing list. And you don’t do that – you use two lists as temporary extra storage.

Your code can be improved:

# your version:
nums[:] = [x for x in nums if x != 0] + [x for x in nums if x == 0]

# improved version
n = len(nums)
nums[:] = [x for x in nums if x]
nums.extend([0]*(n - len(nums)))

Here’s another way which meets the strong version of “in-place”.

n = nums.count(0)
try:
    nums.remove(0)
except ValueError:
    nums.extend([0]*n)

Here’s a third way, very old school, reminds me of writing code in Pascal in the 1990s:

for i in range(len(nums)-1, -1, -1):
    x = nums[i]
    if x == 0:
        del nums[i]

Finally, here’s a clever solution using sorting.

nums.sort(key=lambda x: not x)

I leave it as an exercise to determine which method is the fastest for large lists, say with at least a thousand values.

(My money is on the sort version :slight_smile:

6

Steven, nums.remove(0) removes just a single element. You need to apply remove repeatedly in a loop. IMHO it would be inefficient for large lists because every remove() call will search the list from the beginning.

Also I think it is very important to say that nums.sort(key=lambda x: not x) works correctly only because the sort method does not change the order of items when their ordering keys are equal:

The sort() method is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal.

7

Here is a solution that works “in-place”, if by “in-place” we mean we are only allowed to modify the elements (weird definition, but who knows…)

def bubble_up(L):
    for i in range(len(L)-1, -1, -1):
        if L[i] == 0:
            j = i+1
            while j < len(L) and L[j] != 0:
                L[j-1], L[j] = L[j], L[j-1]
                j += 1
    return L
8

Oops, yes, you are completely right about needing to call nums.remove(0) in a loop. I knew that, and intended to put it in a while loop, but got distracted and forgot. Sorry.

Sorry for any confusion.