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

We iterate all elements, and write to odd or even index based on the parity of the number.

fun sortArrayByParityII(nums: IntArray): IntArray {
    val results = IntArray(nums.size)
    var evenIndex = 0   // 0, 2, 4, 6, ...
    var oddIndex = 1    // 1, 3, 5, ...
    for (num in nums) {
        if (num % 2 == 0) {
            results[evenIndex] = num
            evenIndex += 2
        } else {
            results[oddIndex] = num
            oddIndex += 2
        }
    }
    return results
}

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 index, odd value
odd index, even value

// Correct
even index, even value
odd index, odd value

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.

The problem guarantees that the array length is even and half of the numbers are even, so we can always find the missplaced odd and even elements pair.

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
}