Duplicate Zeros in Kotlin

Question

I am solving a array question.

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Example 1:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]

Example 2:

Input: arr = [1,2,3]
Output: [1,2,3]

I tried this solution but I am getting wrong output

class Solution {
    fun duplicateZeros(arr: IntArray): Unit {
        arr.forEachIndexed { index, value ->
            if(value == 0 && ((arr.size - 1) != index)) {
                arr[index + 1] = 0
            }
        }
    }
}

Actual Output

[1,0,0,0,0,0,0,0]

Expected Output

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

Note please don't make copy of array. I want to solve in same array. Can someone guide me where is my logic is wrong and how can I fix the problem?

Thanks

UPDATE

I tried the code and some test case is working fine and long one is not working correctly..

fun main() {
//    val nums = intArrayOf(1, 0, 2, 3, 0, 4, 5, 0)
//    val nums = intArrayOf(0, 0, 0, 0, 0, 0, 0)
//    val nums = intArrayOf(8, 4, 5, 0, 0, 0, 0, 7)
    val nums = longTestCase()
    var extraSpace = 0
    var temp = nums.lastIndex
    for (i in nums.indices) {
        if (nums[i] == 0) {
            if (i < nums.lastIndex - extraSpace) {
                extraSpace++
            }
        }
    }
    while (temp >= 0) {
        if (nums[temp - extraSpace] == 0 && extraSpace > 0) {
            nums[temp] = 0
            extraSpace--
            temp--
            if (temp >= 0) {
                nums[temp] = 0
            }
        } else {
            nums[temp] = nums[temp - extraSpace]
        }
        temp--
    }
    nums.forEach { print("$it ") }
}


private fun longTestCase(): IntArray {
    return intArrayOf(
        9,
        9,
        9,
        4,
        8,
        0,
        0,
        3,
        7,
        2,
        0,
        0,
        0,
        0,
        9,
        1,
        0,
        0,
        1,
        1,
        0,
        5,
        6,
        3,
        1,
        6,
        0,
        0,
        2,
        3,
        4,
        7,
        0,
        3,
        9,
        3,
        6,
        5,
        8,
        9,
        1,
        1,
        3,
        2,
        0,
        0,
        7,
        3,
        3,
        0,
        5,
        7,
        0,
        8,
        1,
        9,
        6,
        3,
        0,
        8,
        8,
        8,
        8,
        0,
        0,
        5,
        0,
        0,
        0,
        3,
        7,
        7,
        7,
        7,
        5,
        1,
        0,
        0,
        8,
        0,
        0
    )
}

Actual Output

[9,9,9,4,8,0,0,0,3,7,2,0,0,0,0,0,0,0,0,9,1,0,0,0,0,1,1,0,0,5,6,3,1,6,0,0,0,0,2,3,4,7,0,0,3,9,3,6,5,8,9,1,1,3,2,0,0,0,0,7,3,3,0,0,5,7,0,0,8,1,9,6,3,0,0,8,8,8,8,0,0]

Expected output

[9,9,9,4,8,0,0,0,0,3,7,2,0,0,0,0,0,0,0,0,9,1,0,0,0,0,1,1,0,0,5,6,3,1,6,0,0,0,0,2,3,4,7,0,0,3,9,3,6,5,8,9,1,1,3,2,0,0,0,0,7,3,3,0,0,5,7,0,0,8,1,9,6,3,0,0,8,8,8,8,0]

Answer 1

Because OP found a bug in own code in the question, I made a rewrite of that code with some explanation. Code is using same type of logic, which is copying directly to final position in array opposed to e.g shuffling data one position at a time.

Code is tested with initial test dataset and latest long dataset provided by OP in the question, and some misc other input/expected pairs. Code is written inside a Kotest.

given("do/while approach") {

    forAll(
        row(arrayOf(1, 0, 1, 0, 1), arrayOf(1, 0, 0, 1, 0)),
        row(arrayOf(1, 5, 2, 0, 6, 8, 0, 6, 0), arrayOf(1, 5, 2, 0, 0, 6, 8, 0, 0)),
        row(arrayOf(1, 0, 2, 3, 0, 4, 5, 0), arrayOf(1, 0, 0, 2, 3, 0, 0, 4)),
    ) { nums, expected ->

        `when`("duplicating") {

            val zeroIndexesToDuplicate = mutableSetOf<Int>()
            var index = 0

            /** find index positions of zeroes to be duplicated */
            /** keep collecting until no more space in rearranged array */
            do {
                if (nums[index] == 0) {
                    zeroIndexesToDuplicate.add(index)
                }
            } while (++index + zeroIndexesToDuplicate.size < nums.lastIndex)

            /** set insertIndex to end of array */
            var insertIndex = nums.lastIndex

            /** set fetchIndex to first item to fetch from */
            var fetchIndex = insertIndex - zeroIndexesToDuplicate.size

            /** when insertIndex catches up with fetchIndex, no more copying is required */
            /** if no zeros, or just a trailing zero, loop is not entered */
            while (fetchIndex in 0 until insertIndex) {
                nums[insertIndex] = nums[fetchIndex]

                /** if copied item is zero to be duplicated, insert an extra zero */
                if (fetchIndex in zeroIndexesToDuplicate) {
                    nums[--insertIndex] = 0
                }

                /** decrement both indexes */
                fetchIndex--
                insertIndex--
            }

            then("result should be as expected") {
                nums shouldBe expected
            }
        }
    }
}

Answer 2

I would go from right to left, and shift everything right by one step every time I encounter a zero.

Not making copies makes a bit more complicated than needed. If it were a real-world case I would have gone with building a list (copy every item once, and all zero's twice, then take initial list's size elements from newly built list) but I see you are doing this as an excercise

class Solution {
    fun duplicateZeros(arr: IntArray): Unit {
        arr.indices
            .reversed()  // because going from left to right will get you endless zero's as soon as you find a zero
            .drop(1) // because the last item will never move to the right, saves logic in [shiftRightFrom]
            .forEach {
                if (arr[it] == 0)
                    arr.shiftRightFrom(it)
        }
    }

    private fun IntArray.shiftRightFrom(index: Int) {
        ((lastIndex) downTo index + 1).forEach {
            this[it] = this[it - 1] // replace value by it's left neighbour
        }
    }
}