Namaste, I'm Avinash Sharma.

Sort Array By Parity

published on Invalid Date

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]


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]:
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)

Created with ❤️ by Avinash Sharma