Performance of moving zeros to the end of an array programming exercise

Question

I wonder why my solution to this LeetCode "Move Zeros" problem is slower than the majority of other submissions. Is there a better way to approach this problem to make it faster?

The question is as follows:

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. You must do this in-place without making a copy of the array.

Example:

Input: [0,1,0,3,12]

Output: [1,3,12,0,0]

This is my solution:

 func moveZeroes(_ nums: inout [Int]) {
    var index = 0
    for (i,n) in nums.enumerated()
    {
        if n != 0
        {
            nums[index] = n
            index += 1
        }
        
    }
    
    while index < nums.count
    {
        nums[index] = 0
        index += 1
    }
}

LeetCode gives me these statistics:

Runtime: 52 ms, faster than 40.50% of Swift online submissions for Move Zeroes.
Memory Usage: 19.4 MB, less than 13.33% of Swift online submissions for Move Zeroes.

EDIT 1:

If I approach the problem as follows, it does not move the zeros at the end,

EDIT 2:

What about just input.filter { $0 != 0 } + input.filter { $0 == 0 }? — Sulthan
– Sulthan, Commented Feb 25, 2019 at 17:19
i have a similar answer with filter i guessed it was for you also sort can be used but order will be gone — Shehata Gamal
– Shehata Gamal, Commented Feb 25, 2019 at 17:24
What you're looking for here is called a stable partitioning. stackoverflow.com/q/40010345/3141234 — Alexander
– Alexander, Commented Feb 25, 2019 at 18:53
FYI, don't trust the numbers. I am pretty sure they don't even run optimized code and it seems most of the 40ms second is actually the time for starting the performance test and the actual test is almost instant. — Sulthan
– Sulthan, Commented Feb 25, 2019 at 22:22

ielyamani · Accepted Answer · 2019-02-25 21:03:01Z

2

Here is 36ms in-place solution for you :

class Solution {
    func moveZeroes(_ nums: inout [Int]) {

        if nums.count < 2 {
            return
        }

        var j = 0

        while j < nums.count, nums[j] != 0 {
            j += 1
        }

        if j < nums.count - 1 {
            for i in j+1..<nums.count {
                if nums[i] != 0 {
                    nums.swapAt(i, j)
                    j += 1
                }
            }
        }
    }
}

edited Feb 25, 2019 at 21:03

answered Feb 25, 2019 at 20:34

ielyamani

18.6k11 gold badges59 silver badges94 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Sulthan Over a year ago

I wouldn't worry too much about individual ms. There is probably a pretty big tolerance since the same solution submitted multiple times has different results (+10ms in my testing). Unfortunately, most of the memory usage is probably the Swift runtime therefore small differences are also unreliable.

Sulthan Over a year ago

Actually, it seems that it takes about 40ms for the performance test to start and the actual test is almost instantaneous. What a bad performance test! I would say it's not even optimized.

jscs · Accepted Answer · 2019-02-25 17:28:48Z

2

From what I can see, it's likely other submissions are doing this

Check and count 0's in string
Remove 0's
Replace number of 0's at the end of the string

A logical method no doubt, but I'd say yours just picks the basic needs of the challenge and goes for it.

edited Feb 25, 2019 at 17:28

jscs

64k13 gold badges155 silver badges200 bronze badges

answered Feb 25, 2019 at 17:15

Badja

8851 gold badge10 silver badges36 bronze badges

Comments

Sulthan · Accepted Answer · 2019-02-25 18:19:31Z

1

I would personally use:

input = input.filter { $0 != 0 } + input.filter { $0 == 0 }

which can be simplified to one pass:

let nonZeros = input.filter { $0 != 0 }
input = nonZeros + Array(repeating: 0, count: input.count - nonZeros.count)

EDIT: The simplest version without creating a new array would be some primitive version of bubble sort, e.g.:

var numZeros = 0

// iterate array from start to end
for (offset, element) in input.enumerated() {
    if element == 0 {
        // count every zero
        numZeros += 1
    } else if numZeros > 0 {
        // move every non-zero element left
        input[offset - numZeros] = element    
        // replace with zero
        input[offset] = 0
    }
}

edited Feb 25, 2019 at 18:19

answered Feb 25, 2019 at 17:23

Sulthan

130k23 gold badges223 silver badges277 bronze badges

6 Comments

casillas Over a year ago

Sorry, I forgot to mention in the question that You must do this in-place without making a copy of the array.

Sulthan Over a year ago

@hotspring That means you have to use some kind of bubble sort I guess.

Shehata Gamal Over a year ago

@hotspring the duplicate same and was for you also

casillas Over a year ago

@Sh_Khan, please check my edit referring to screenshot.

casillas Over a year ago

@Sulthan, could you please check my edit referring to screnshot at the bottom.

|

vadian · Accepted Answer · 2019-02-25 19:14:08Z

Another approach is the half-stable-partition algorithm. The benefit is the items are swapped rather than removed and inserted/appended.

Half-stable means the order of the left side of the split point is preserved.

extension Array {

    mutating func halfStablePartition(indexes : IndexSet) { // code is O(n)
        guard var i = indexes.first, i < count else { return }
        var j = index(after: i)
        var k = indexes.integerGreaterThan(i) ?? endIndex
        while j != endIndex {
            if k != j { swapAt(i, j); formIndex(after: &i) }
            else { k = indexes.integerGreaterThan(k) ?? endIndex }
            formIndex(after: &j)
        }
    }
}

var input = [0,1,0,3,12]

let indices = IndexSet(input.indices.filter{input[$0] == 0})
input.halfStablePartition(indexes: indices)

Leo Dabus · Accepted Answer · 2019-02-25 23:27:07Z

1

Swift 4.2 or later using removeAll mutating method:

Mutating the input:

class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        var counter = 0
        nums.removeAll {
            if $0 == 0 {
                counter += 1
                return true
            }
            return false
        }
        nums += repeatElement(0, count: counter)
    }
}

A similar approach for Swift 4.1 or earlier

func moveZeroes(_ nums: inout [Int]) {
    var counter = 0
    nums.indices.reversed().forEach {
        if nums[$0] == 0 {
            counter += 1
            nums.remove(at: $0)
        }
    }
    nums += repeatElement(0, count: counter)
}

var input = [0,1,0,3,12]
moveZeroes(&input)
input   // [1, 3, 12, 0, 0]

Non mutating approach:

func moveZeroes(_ nums: [Int]) -> [Int] {
    var counter = 0
    return nums.filter {
        if $0 == 0 { counter += 1 }
        return $0 != 0
    } + repeatElement(0, count: counter)
}

let  input = [0,1,0,3,12]

let zerosMoved = moveZeroes(input)
zerosMoved   // [1, 3, 12, 0, 0]

edited Feb 25, 2019 at 23:27

answered Feb 25, 2019 at 17:44

Leo Dabus

238k61 gold badges512 silver badges625 bronze badges

3 Comments

casillas Over a year ago

It is really nice approach but cannot handle one scenario which I attached into the my question as EDIT 2

Sulthan Over a year ago

pretty sure you would have to iterate from the end. However, removing elements from the middle of the array is probably worse than a simple filter.

Leo Dabus Over a year ago

@Sulthan yes if I were not appending the removed element to the end of the array.

Eugene Pavlov · Accepted Answer · 2020-12-13 02:13:59Z

1

For modifying array in place, and keeping it:

O(n) for Time Complexity

O(1) for Space Complexity

Cracked my head way to long for this one. The cleanest way if you swap element that is NOT zero:

func moveZeroes(_ nums: inout [Int]) {
    // amount of swaps, will be used a as reference for next swap index
    var j = 0 
    
    for (i, e) in nums.enumerated() {
        if e != 0 {
            nums.swapAt(j, i)
            j += 1
        }
    }
    
}

answered Dec 13, 2020 at 2:13

Eugene Pavlov

6985 silver badges19 bronze badges

Comments

Cristik · Accepted Answer · 2019-02-25 21:54:25Z

0

One fast solution is to shift non-zero elements to the left by the amount of zeros encountered until then:

func moveZeroes(_ nums: inout [Int]) {
    var offset = 0
    for i in 0..<nums.count {
        if nums[i] == 0 { offset += 1 }
        else { nums.swapAt(i, i-offset) }
    }
}

This solution takes exactly N steps, and at each step we either perform an addition, or a swap, which are both quite fast.

Your solution, on the other hand required two iterations, resulting in 2*N steps, which is why it was slower than other solutions.

answered Feb 25, 2019 at 21:54

Cristik

33.2k26 gold badges106 silver badges144 bronze badges

3 Comments

Leo Dabus Over a year ago

nums.indices.forEach { nums[$0] == 0 ? offset += 1 : nums.swapAt($0, $0 - offset) }

Sulthan Over a year ago

I have used exactly the same solution, with a manual assign instead of swapAt. To be honest, Actually, I have done some performance testing and all the solutions have almost the same performance. Of course, you can improve slightly using microoptimizations (removing function calls) but you need an array with 10M elements to really see a meaningful difference (0.02 sec in my testing)

Cristik Over a year ago

@Sulthan I think the numbers are similar because all answers are O(N). Some of the solutions use more than N steps due to implementation details, however as you said the time difference is not noticeable for small to medium arrays.

Collectives™ on Stack Overflow

Performance of moving zeros to the end of an array programming exercise

7 Answers 7

2 Comments

Comments

6 Comments

Comments

3 Comments

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

2 Comments

Comments

6 Comments

Comments

3 Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related