How about the recursive code for "Find Zero" I've written?

Question

Here's the problem:

Given an array nums, write a function that moves all 0s to the end of the array while maintaining the relative order of the non-zero elements. Please note that the array must be modified in place without creating a copy of the array.

Does this code take linear time? If not, should I write the code in a more normal way using two pointers?

'''Recursively solve the 'Find Zero' problem without a new array created.'''

def Min_Zero(j, nums):
    while nums[j] != 0 and j < len(nums)-1:
        j += 1
    return j

def Min_Not_Zero(i, nums):
    while nums[i] == 0 and i < len(nums)-1:
        i += 1
    return i

# Swap the first zero element with the first non-zero element which is latter than the first zero element
def Swap_Zero(i=0, j=0, nums=[1, 2, 3, 4, 5, 0, 0, 0, 6, 0, 7, 0, 8, 0, 0, 9, 0, 0]):
    n = Min_Zero(j, nums)
    m = Min_Not_Zero(n, nums)
    if m < len(nums)-1 and n < len(nums)-1 and m > n:
        nums[m], nums[n] = nums[n], nums[m]
        Swap_Zero(m, n, nums = nums)
    return nums

Swap_Zero()

I've successfully run the code. It's verified.

Answer 1

Yes, it's linear. (@matszwecja: On each iteration the functions Min_Zero and Min_Not_Zero start at the same index at which they ended in the previous run, so in total each iterates the array only once).

I've successfully run the code. It's verified.

No, it's not. You ran the code with one (or a couple of examples). It breaks if you call it with [1, 0, 1].

The parameter i in Swap_Zero is unused.

The code is convoluted.

It more or less already implements the algorithm suggested by @Martin Brown, but in a way that is too complicated. You do not need recursion here.

@Martin Brown: Why should it be more complicated if the 0 have to come first? The situation is completely symmetrical. There is one set of characters that should be moved to the front. In one case it's all character except for "0", in the other case it is the single character "0".

This is the simplest code I could come up with. No guarantee, though, test it yourself ;_)

def move_zeros_to_end(nums):
    index = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            if index != i:
                nums[index] = nums[i]
                nums[i] = 0
            index += 1