Domain 1EasyCORE

Sort Array By Parity II

The problem requires sorting an array such that all even-indexed positions contain even numbers and all odd-indexed positions contain odd numbers. The input is an array of integers where exactly half are even and the other half are odd. The output should be any permutation of the input array that satisfies the parity condition.

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

922. Sort Array By Parity II

Model: qwen2.5-coder:14b
Topics: Array,Sort
FAANG asked: 1
Acceptance rate: 70.7%


Problem Breakdown

The problem requires sorting an array such that all even-indexed positions contain even numbers and all odd-indexed positions contain odd numbers. The input is an array of integers where exactly half are even and the other half are odd. The output should be any permutation of the input array that satisfies the parity condition.

Inputs:

  • An array nums of integers with length between 2 and 20,000.
  • Each integer in nums is between 0 and 1000.

Outputs:

  • A sorted array where even indices contain even numbers and odd indices contain odd numbers.

Implicit Constraints:

  • The array length is always even.
  • There are no negative numbers or duplicates that need special handling.

Intuition

A brute-force approach would involve generating all permutations of the array and checking each one to see if it satisfies the parity condition. This is computationally expensive with a time complexity of O(n!) due to the factorial number of permutations.

The key insight is to use a two-pointer technique to swap elements in place, ensuring that we maintain the parity condition as we iterate through the array. This approach leverages the fact that there are exactly half even and half odd numbers, allowing us to efficiently correct any misplaced elements.

Approach

  1. Initialize two pointers: even_ptr starting at 0 (for even indices) and odd_ptr starting at 1 (for odd indices).
  2. Iterate through the array:
    • If the element at even_ptr is odd, swap it with the element at odd_ptr.
    • Move odd_ptr to the next odd index.
  3. Continue this process until both pointers have traversed the entire array.

This approach ensures that all even numbers are placed at even indices and all odd numbers are placed at odd indices in a single pass through the array.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. We make a single pass through the array, performing constant-time operations for each element.
  • Space Complexity: O(1). The algorithm uses only a fixed amount of extra space (for the two pointers).

Solution

def sortArrayByParityII(nums):
    even_ptr = 0
    odd_ptr = 1
    
    while even_ptr < len(nums) and odd_ptr < len(nums):
        if nums[even_ptr] % 2 != 0:
            # Swap the elements at even_ptr and odd_ptr
            nums[even_ptr], nums[odd_ptr] = nums[odd_ptr], nums[even_ptr]
            # Move odd_ptr to the next odd index
            odd_ptr += 2
        else:
            # Move even_ptr to the next even index
            even_ptr += 2
    
    return nums

Edge Cases Handled

  • All Even Numbers: The algorithm will correctly place all numbers at even indices since there are no odd numbers to swap.
  • All Odd Numbers: Similarly, all numbers will be placed at odd indices.
  • Mixed Even and Odd Numbers: The two-pointer technique ensures that misplaced numbers are swapped in a single pass, maintaining the parity condition.