905. Sort Array By Parity

Problem¶

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

Example 1:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

1 <= nums.length <= 5000
0 <= nums[i] <= 5000

Solve¶

Quick sort like partitioning odd/even - Or Two pointer¶

O(n)

Start left and right, swap every odd/ even found until left > right
Implement in both Python and Go.

Time Submitted	Status	Runtime	Memory	Language
09/28/2023 18:24	Accepted	9 ms	4.8 MB	golang
09/28/2023 18:21	Accepted	81 ms	17 MB	python3

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        l = 0
        r = len(nums)-1
        while l < r:
            while nums[l] % 2 == 0 and l < r:
                l = l + 1
            while nums[r] % 2 == 1 and l < r:
                r = r - 1

            if l < r:
                nums[l], nums[r] = nums[r], nums[l]
            l = l + 1
            r = r - 1

        return nums

func sortArrayByParity(nums []int) []int {
    l := 0
    r := len(nums)-1
    for l < r {
        for nums[l] % 2 == 0 && l < r {
            l = l + 1
        }
        for nums[r] % 2 == 1 && l < r {
            r = r - 1
        }
        if l < r {
            nums[l], nums[r] = nums[r], nums[l]
        }
        l = l + 1
        r = r - 1
    }

    return nums
}

Last update : September 28, 2023
Created : September 28, 2023