LC905 Sort Array By Parity

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        # time O(N) space O(N)
        # main idea: assign number to odd,even list seperately and link two lists together
        even = []
        odd = []
        for num in A:
            if num % 2 != 0:
                odd.append(num)
            else:
                even.append(num)
        even.extend(odd)
        return even

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        # time O(N) space O(N)
        # main idea: two ptr, run from both ends, if end is odd and beginning is even, swap them 
        # step1: initiallize two ptr  and set termination condition: l = r 
        l, r = 0, len(A)-1
        while l < r:
        # step2: if left is odd and right is even , swap   !! note the comparison need to be in the beginning or it need to decrement/increment before going to next loop
            if A[l] % 2 > A[r] % 2:
                A[l], A[r] = A[r], A[l] 
        # step3: if left is even, go to next position; similar for right 
            if A[l] % 2 == 0:
                l += 1 
            if A[r] % 2 != 0:
                r -= 1
        return A