LeetCode Solutions Blog

Sort Array By Parity

Number: 941

Difficulty: Easy

Paid? No

Problem Description

Given an integer array, rearrange its elements so that all even integers appear before all odd integers. The resulting array can be in any order as long as the even numbers come first.

Key Insights

The problem can be efficiently solved in one pass with a two-pointer strategy.
In-place swapping allows partitioning the array with O(1) extra space.
If a number is even, it belongs to the front section; if it is odd, it belongs at the back.

Space and Time Complexity

Time Complexity: O(n) - We traverse the array once. Space Complexity: O(1) - In-place partitioning requires no additional data structures.

Solution

We use a two-pointers approach: one pointer starts at the beginning (leftPointer) and the other at the end (rightPointer). The leftPointer moves forward when it finds an even number, while the rightPointer moves backward when it finds an odd number. When leftPointer finds an odd number and rightPointer finds an even number, we swap the two. This process continues until the pointers meet, ensuring that all even numbers are at the beginning and odd numbers at the end.

Code Solutions

# Function to sort array by parity
def sortArrayByParity(nums):
    # Initialize two pointers
    leftPointer = 0
    rightPointer = len(nums) - 1

    # Process elements until pointers meet
    while leftPointer < rightPointer:
        # If left is even, it's in the correct place, move pointer to the right
        if nums[leftPointer] % 2 == 0:
            leftPointer += 1
        # If right is odd, it's in the correct place, move pointer to the left
        elif nums[rightPointer] % 2 == 1:
            rightPointer -= 1
        # Swap the odd number on the left with the even number on the right
        else:
            nums[leftPointer], nums[rightPointer] = nums[rightPointer], nums[leftPointer]
            leftPointer += 1
            rightPointer -= 1

    # Return the rearranged array
    return nums

# Example usage:
print(sortArrayByParity([3, 1, 2, 4]))