Problem Statement

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition. URL

Example 1:

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

Note:

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

Approach 1

Appending Even and Odd isolated arrays

#collapse-hide

from typing import List

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        return [i for i in A if i%2 == 0] + [i for i in A if i%2 != 0]

sol = Solution()
sol.sortArrayByParity([3,1,2,4])

[3, 1, 2, 4]

Worst case performance in Time: $O(2n)$

Approach 2

Traversing from first and last conditionally

#collapse-hide

from typing import List

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        if len(A) == 0:
            return []
        if len(A) == 1:
            return [A[0]]
        result = [0]*len(A)
        i = 0
        j = len(A)-1
        for num in A:
            if num % 2 == 0:
                result[i] = num
                i += 1
            else:
                result[j] = num
                j -= 1
        return A

sol = Solution()
sol.sortArrayByParity([3,1,2,4])

[3, 1, 2, 4]

Worst case performance in Space: $O(n)$

Apporach 3

Traversing from first and last conditionally with swap operations along existing input array

#collapse-hide

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        i = 0
        j = len(A)-1
        while(i<j):
            if A[i]%2 != 0:
                A[i], A[j] = A[j], A[i]
                j -= 1
            else:
                i += 1
        return A

sol = Solution()
sol.sortArrayByParity([3,1,2,4])

[4, 2, 1, 3]

Worst case performance in Time: $O(n)$

Worst case performance in Space: $O(1)$