922.sort-array-by-parity-ii.md

922. Sort Array By Parity II

Test Cases

index = 0, 1, 2, 3
value = 0, 1, 2, 3
        O  O  O  O

        0, 1, 3, 2
        O  O  X  X

        3, 2, 1, 0
        X  X  X  X

With Extra Space

fun sortArrayByParityII(nums: IntArray): IntArray {
    val n = nums.size
    
    var oddIndex = 0
    val odds = IntArray(n)
    var evenIndex = 0
    val evens = IntArray(n)
    for (num in nums) {
        if (num % 2 == 0) {
            evens[evenIndex++] = num
        } else {
            odds[oddIndex++] = num
        }
    }
    oddIndex = 0
    evenIndex = 0
    for (i in nums.indices) {
        nums[i] = if (i % 2 == 0) evens[evenIndex++]
        else odds[oddIndex++]
    }
    return nums
}

In-Place

Idea!! Use two pointers to search for missplaced odd and even elements even(odd) and odd(even), and swap them.

// Missplaced odd and even elements
even
odd

odd
even

// Correct
even
even

odd
odd

We iterate all the number and find the first even number that is NOT at even index, and the first odd number that is NOT at odd index. Then we swap them. This ensures that the even index gets an even number and the odd index gets an odd number.

fun sortArrayByParityII(nums: IntArray): IntArray {
    val n = nums.size
    var evenIndex = 0
    var oddIndex = 1
    while (evenIndex < n && oddIndex < n) {
        // Find the first even number that is NOT at even index
        while (evenIndex < n && nums[evenIndex] % 2 == 0) {
            evenIndex += 2
        }
        // Find the first odd number that is NOT at odd index
        while (oddIndex < n && nums[oddIndex] % 2 != 0) {
            oddIndex += 2
        }

        // We need to check if it's still in the range because
        // it may be out of bounds if every number is already at the correct index
        if (evenIndex < n && odd < n) {
            // Now A[evenIndex] is odd, and A[oddIndex] is even, swap them
            nums.swap(oddIndex, evenIndex)
        }
    }
    return nums
}

// Or equivalently
fun sortArrayByParityII(nums: IntArray): IntArray {
    var evenIdx = 0
    var oddIdx = 1
    val n = nums.size

    while (evenIdx < n && oddIdx < n) {
        if (nums[evenIdx] % 2 == 0) {
            evenIdx += 2  // Correctly placed, move forward
        } else if (nums[oddIdx] % 2 == 1) {
            oddIdx += 2  // Correctly placed, move forward
        } else {
            // Swap misplaced values
            nums[evenIdx] = nums[oddIdx].also { nums[oddIdx] = nums[evenIdx] }
            evenIdx += 2
            oddIdx += 2
        }
    }
    return nums
}