Domain 1EasyCORE

Sort Array By Parity

The problem requires sorting an array such that all even numbers come before any odd numbers. The input is a non-empty array of non-negative integers. The output should be any permutation of the input array where even numbers precede odd numbers. There are no implicit constraints regarding duplicates or negative numbers since the problem specifies non-negative integers.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

905. Sort Array By Parity

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 75.0%


Problem Breakdown

The problem requires sorting an array such that all even numbers come before any odd numbers. The input is a non-empty array of non-negative integers. The output should be any permutation of the input array where even numbers precede odd numbers. There are no implicit constraints regarding duplicates or negative numbers since the problem specifies non-negative integers.

Intuition

A brute-force approach would involve iterating through the array twice: once to collect all even numbers and another to collect all odd numbers, then concatenating these two lists. This approach is straightforward but inefficient with a time complexity of O(n) for collecting elements and O(n) for concatenation, resulting in an overall time complexity of O(2n), which simplifies to O(n). However, it uses additional space proportional to the size of the input array.

A more efficient approach involves using two pointers or indices to partition the array in a single pass. The key insight is that we can maintain two pointers: one starting at the beginning of the array (for placing even numbers) and another starting just after the end of the array (for placing odd numbers). As we iterate through the array, we swap elements to ensure all even numbers are moved to the front and all odd numbers are moved to the back.

Approach

We will use a two-pointer technique to partition the array:

  1. Initialize two pointers: left at the start of the array and right just after the end of the array.
  2. Iterate through the array with a pointer i.
  3. If the element at A[i] is even, increment both left and i.
  4. If the element at A[i] is odd, swap it with the element at right, then decrement right.
  5. Continue this process until i surpasses right.

This approach ensures that all even numbers are moved to the front of the array and all odd numbers are moved to the back in a single pass.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. We make a single pass through the array.
  • Space Complexity: O(1). The algorithm uses only a constant amount of extra space for the pointers and does not require additional data structures.

Solution

def sortArrayByParity(A):
    left, right = 0, len(A) - 1
    
    while left <= right:
        if A[left] % 2 == 0:
            left += 1
        else:
            A[left], A[right] = A[right], A[left]
            right -= 1
    
    return A

Edge Cases Handled

  • All Even Numbers: If the array contains only even numbers, the left pointer will traverse the entire array without any swaps.
  • All Odd Numbers: If the array contains only odd numbers, the right pointer will traverse the entire array without any swaps.
  • Single Element Array: The algorithm handles arrays with a single element correctly by not performing any swaps.
  • Empty Array: Although the problem specifies that the input array is non-empty, if we were to extend this solution to handle an empty array, it would naturally return an empty array without any modifications.