905.sort-array-by-parity.md

905. Sort Array By Parity

Two Pointers with Extra Space

We just create an extra space to store the even add odd numbers at left and right side of the output array.

def sortArrayByParity(self, nums: List[int]) -> List[int]:
    n = len(nums)
    results = [0] * n
    even_index = 0
    odd_index = n - 1
    for i in range(0, n):
        if nums[i] % 2:
            results[odd_index] = nums[i]
            odd_index -= 1
        else:
            results[even_index] = nums[i]
            even_index += 1
    return results

fun sortArrayByParity(nums: IntArray): IntArray {
    val results = IntArray(nums.size)
    var evenIndex = 0
    var oddIndex = nums.size - 1
    for (i in 0 until nums.size) {
        if (nums[i] % 2 == 0) {
            results[evenIndex] = nums[i]
            evenIndex++
        } else {
            results[oddIndex] = nums[i]
            oddIndex--
        }
    }
    return results
}

• Time Complexity: O(n) for only one for-loop.
• Space Complexity: O(n) for extra result array.

Two Pointers by Swapping Even Numbers to the Left Part

Idea!! We iterate all elements, and swap the even number to the left part.

Iterate the elements by read pointer, initialize even index at the first element, then there are two cases:

• If the current number is even, then swap with the element at even index.
• If the current number is odd, then keep iterating.

[1, 2, 4, 3]
 E
 R
[1, 2, 4, 3]
 E
    R
[2, 1, 4, 3]
    E
       R
[2, 4, 1, 3]
       E
          R

def sortArrayByParity(self, nums: List[int]) -> List[int]:
    even_index = 0
    for read in range(0, len(nums)):
        if nums[read] % 2 == 0:
            nums[even_index], nums[read] = nums[read], nums[even_index]
            even_index += 1
    return nums

fun sortArrayByParity(nums: IntArray): IntArray {
    var evenIndex = 0
    for (readIndex in 0 until nums.size) {
        if (nums[readIndex] % 2 == 0) {
            swap(nums, readIndex, evenIndex)
            evenIndex++
        }
    }
    return nums
}

private fun swap(nums: IntArray, left: Int, right: Int) {
    val temp = nums[left]
    nums[left] = nums[right]
    nums[right] = temp
}

• Time Complexity: O(n) for only one for-loop.
• Space Complexity: O(1) no extra space.

Two Pointers by Swapping Odd Number to the Right Part

Idea!! We iterate all elements, and swap odd number to the right part.

Iterate the elements by read pointer, initialize odd index at the last element, then there are two cases:

• If the current number is odd, then swap with the element at odd index. But we don't know if the element at odd index is even or odd, so we keep swapping until the element at odd index is even. Or we can check the element at odd index is even or odd, if it's odd, when we move odd to previous element.
• If the current number is even, just skip and move to next iteration.

[2, 4, 1, ... 8, 3, 5]
       R            O   // swap 1, 5
       5, ... 8, 3, 1   // but 5 is odd, so we keep swapping
       R         O
       3, ... 8, 5, 1   // but 3 is odd, so we keep swapping
       R      O
       8, ... 3, 5, 1   // 8 is even, so we stop swapping

def sortArrayByParity(self, nums: List[int]) -> List[int]:
    n = len(nums)
    read_index, odd_index = 0, n - 1
    while read_index <= odd_index:
        if nums[read_index] % 2:
            nums[read_index], nums[odd_index] = nums[odd_index], nums[read_index]
            odd_index -= 1
        else:
            read_index += 1
    return nums

fun sortArrayByParity(nums: IntArray): IntArray {
    var readIndex = 0
    var oddIndex = nums.size -1
    while (readIndex <= oddIndex) {
        if (nums[readIndex] % 2 != 0) {
            swap(nums, readIndex, oddIndex)
            oddIndex--
        } else {
            readIndex++
        }

        // Or we can skip the odd number at the end.
        // if (nums[readIndex] % 2 != 0) {
        //     if (nums[oddIndex] % 2 == 0) {
        //         swap(nums, readIndex, oddIndex)
        //     }
        //     oddIndex--
        // } else {
        //     readIndex++
        // }
    }
    return nums       
}

private fun swap(nums: IntArray, left: Int, right: Int) {
    val temp = nums[left]
    nums[left] = nums[right]
    nums[right] = temp
}

• Time Complexity: O(n) for only one for-loop.
• Space Complexity: O(1) no extra space.