Sort Array By Parity

Difficulty: Easy | Acceptance: 76.50% | Paid: No Topics: Array, Two Pointers, Sorting

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.

• Examples
• Constraints
• Two Pointers
• Extra Space
• In-place Partition

Examples

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

Two Pointers

Intuition Use two pointers starting from opposite ends of the array. The left pointer finds odd numbers while the right pointer finds even numbers, then swap them.

Steps

• Initialize left pointer at index 0 and right pointer at the last index
• Move left pointer forward while it points to an even number
• Move right pointer backward while it points to an odd number
• Swap elements at left and right pointers when left points to odd and right points to even
• Continue until pointers meet or cross

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal in-place solution with minimal swaps

Extra Space

Intuition Create a new array and first add all even numbers, then add all odd numbers from the original array.

Steps

• Initialize an empty result array
• Iterate through the input array and add all even numbers to result
• Iterate through the input array again and add all odd numbers to result
• Return the result array

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        result = []
        for num in nums:
            if num % 2 == 0:
                result.append(num)
        for num in nums:
            if num % 2 == 1:
                result.append(num)
        return result

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Simple and readable but uses extra memory

In-place Partition

Intuition Use a single pointer to track where the next even number should be placed, similar to the partition step in quicksort.

Steps

• Initialize a pointer j at index 0
• Iterate through the array with pointer i
• When nums[i] is even, swap it with nums[j] and increment j
• Continue until the end of the array

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Clean in-place solution with single pass