CODEWITHSUNDEEP
pythonarraysalgorithm
JM Lontoc
JM Lontoc

Reputation: 23

Put all non zero values at the right of an array

I have an fixed size array of n elements containing integers. I want to put all the non zero values at the right side of the array.

Examples:

[1, 0, 0, 4] => [0, 0, 1, 4]
[2, 0, 4, 3] => [0, 2, 4, 3]
[1, 0, 0] => [0, 0, 1]

What would be a simple algorithm to perform this?

This is what I currently have but it only shifts the element at index to right

def slide(arr):

    i = len(arr) - 2
    while i >= 0:

        if arr[i] != 0 and arr[i + 1] == 0:
            arr[i + 1] = arr[i]
            arr[i] = 0

        i -= 1

    print(arr)

Upvotes: 1

Views: 93

Answers (3)

sebastian
sebastian

Reputation: 412

Create a new array, same size, initialized with 0's.

Scan the first array:
    if the current element is not zero:
        copy it into the second array starting from the end

Time complexity: O(n) Space complexity: O(n)

straightforward and intuitive approach

Upvotes: 1

MBo
MBo

Reputation: 80187

To shift values right with their initial order: (inplace, linear time complexity)

def slide(arr):
    zeros = 0
    for i in range(len(arr) - 1, -1, -1):
        if arr[i] == 0:
            zeros += 1
        else:
            arr[i+zeros] = arr[i]
    for i in range(zeros):
        arr[i] = 0
    print(arr)

slide([1,0,2,0,0,3])

>>[0, 0, 0, 1, 2, 3]

Upvotes: 2

Aemyl
Aemyl

Reputation: 2194

I would count the zeros, remove them and include them at the beginning:

zeros = [0] * arr.count(0)
while 0 in arr:
    arr.remove(0)
arr = zeros + arr

Upvotes: 2

Related Questions