HàPhan 河

Day 4 of 30 days Leetcode challenge

Move Zeros

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.

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

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.


Solution:

1 : use two pointers, swap if lower value is zero and faster is not.
O(2n)

class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        var lower = 0
        var faster = 1

        while faster < nums.count {
            if nums[lower] == 0 {
                if nums[faster] != 0 {
                    nums.swapAt(lower,faster)
                    lower += 1
                }
                faster += 1
            }else{
                lower += 1
                if faster == lower {
                    faster += 1
                }
            }
        }
    }
}

2 : More tricky. Pick non-zero values and override from left to right of the array. One more loop to fill the rest indexes to zeroes.
O(2n)

class Solution {
    func moveZeroes(_ nums: inout [Int]) {
         var counter = 0
         for val in nums {
             if val != 0 {
                 nums[counter] = val
                 counter += 1
             }
         }
         
         //fill the rest
         for i in counter..<nums.count {
             nums[i] = 0
         }
    }
}

Comments