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

1. solution

• Think of dividing the array in two equal parts.
• such that the left part is all even numbers and the right part is all odd numbers.
• Finally, return the merger of two parts.

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        even,odd=[],[]
        for i in nums:
            even.append(i) if i%2==0 else odd.append(i)
        return even+odd

Time complexity: O(N)

Space complexity: O(N)

2. Solution

• Two points approch to solve this problem.
• We will update the array when the following is true:
  • nums of left is grater than the right the swap the nums[right] to nums[left]
  • if nums of left is even increment the left pointer by 1.
  • if nums of right is even decrement the right pointer by 1.

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

Time complexity: O(log(N))

Space complexity: O(1)