283.move-zeros.md

283. Move Zeroes

Two Pointers

Iterate all element, just write non-zero items (skip zero items), and append zero at the last.

fun moveZeros(nums: IntArray) {
    var readIndex = 0
    var writeIndex = 0 // The next position to write
    while (readIndex < nums.size) {
        if (nums[readIndex] != 0) {
            nums[writeIndex] = nums[readIndex]
            writeIndex++
        }
        readIndex++
    }
    while (writeIndex < nums.size) {
        nums[writeIndex] = 0
        writeIndex++
    }
}

fun moveZeroes(nums: IntArray): Unit {
    var write = -1 // The current written position 
    for (read in nums.indices) {
        if (nums[read] != 0) nums[++write] = nums[read]
    }
    for (i in write + 1 until nums.size) {
        nums[i] = 0
    }
}

• Time Complexity: O(n) for two while loops but iterating the most n element.
• Space Complexity: O(1), no extra space required.

Swap

fun moveZeroes(nums: IntArray): Unit {
    var zeroLength = 0
    for (i in 0 until nums.size) {
        val value = nums[i]
        if (value == 0) {
            zeroLength++
        } else if (zeroLength > 0) { // If we have zero item
            nums[i - zeroLength] = value
            nums[i] = 0
        } 
    }
}