CODEWITHSUNDEEP
pythonarrays
nomeron
nomeron

Reputation: 43

Move element to end of array

I have the following question (from AlgoExpert):

You're given an array of integers and an integer. Write a function that moves all instances of that integer in the array to the end of the array and returns the array. The function should perform this IN-PLACE and doesn't need to maintain the order of the other integers.

For example:

array = [2,1,2,2,2,3,4,2]
toMove = 2

Expected = [1,3,4,2,2,2,2,2] 
           (the numbers 1,3,4 could be ordered differently)

My code:

def moveElementToEnd(array, toMove):
    l = 0
    r = len(array) - 1
    while l < r:
        if array[l] == toMove and array[r] == toMove:
            r -= 1
        elif array[l] != toMove and array[r] != toMove:
            l += 1
        elif array[l] == toMove and array[r] != toMove:
            array[l], array[r] = array[r], array[l]
            l += 1
            r -= 1
    return array

This gets timed out, but when I change the if statements as follows, it works fine:

def moveElementToEnd(array, toMove):
    if len(array) < 1:
        return array
    l = 0
    r = len(array) - 1
    while l < r:
        if array[l] == toMove and array[r] != toMove:
            array[l], array[r] = array[r], array[l]
            l += 1
            r -= 1      
        elif array[l] != toMove and array[r] != toMove:
            l += 1
        else:
            r -= 1
    return array

What causes the timeout in the first code snippet?

Upvotes: 0

Views: 1137

Answers (2)

trincot
trincot

Reputation: 350212

Your first code block can give an infinite loop, as there are cases where the loop does not change either of the indexes. This is because your if ..elif.. construct has no catch-all at the end (using else)

So it is this part that has a problem:

        if array[l] == toMove and array[r] == toMove:
            r -= 1
        elif array[l] != toMove and array[r] != toMove:
            l += 1
        elif array[l] == toMove and array[r] != toMove:
            array[l], array[r] = array[r], array[l]
            l += 1
            r -= 1

It doesn't do anything when array[l] != toMove and array[r] == toMove, and so the loop will run infinitely.

You can picture the four possibilities as follows:

array[r] == toMove array[r] != toMove
array[l] == toMove 1 2
array[l] != toMove 3 4

Your faulty code deals with cases 1, 4 and 2 (in that order), but not with 3

The working code deals with cases 2 and 4 first, and in the final else it deals with cases 1 and 3 together.

What you want to happen in those four cases is:

array[r] == toMove array[r] != toMove
array[l] == toMove r-=1 swap, l+=1; r-=1
array[l] != toMove r-=1 l+=1

The fix for your code is thus to change this:

if array[l] == toMove and array[r] == toMove:

to this:

if array[r] == toMove:

So it deals with two cases in one go.

And with that change, the second condition can be simplified: if execution gets there, we know that array[r] != toMove, so it does not need to be tested. It is also no longer needed to have a second elif condition, as that condition will be true whenever the execution gets there. You can change it to an else.

    if array[r] == toMove:
        r -= 1
    elif array[l] != toMove:
        l += 1
    else:
        array[l], array[r] = array[r], array[l]
        l += 1
        r -= 1

And this version is even more concise than the working version you presented.

Upvotes: 1

Cory Kramer
Cory Kramer

Reputation: 117856

You can use sort with a custom key that compares each element to toMove. All the False values will be to the left, and all the True values will be to the right. Therefore all the toMove values will end up at the back of the list.

>>> array = [2,1,2,2,2,3,4,2]
>>> toMove = 2
>>> array.sort(key=lambda i: i == toMove)
>>> array
[1, 3, 4, 2, 2, 2, 2, 2]

Upvotes: 4

Related Questions