Sort Array By Parity II

Problem Description

Given an array of integers nums where half the numbers are even and the other half are odd, rearrange the array so that whenever nums[i] is even, the index i is even, and whenever nums[i] is odd, the index i is odd. Return any valid rearranged array.

Key Insights

• The array has an equal number of even and odd numbers.
• Even-indexed positions must hold even numbers, and odd-indexed positions must hold odd numbers.
• A two-pointer method can be employed to swap misplaced elements.
• By iterating only over even and odd indices separately, we achieve an efficient in-place solution.

Space and Time Complexity

Time Complexity: O(n) – We scan through the array with two pointers. Space Complexity: O(1) – The sorting is performed in-place without using extra space.

Solution

We use two pointers:

1. An evenIndex starting at 0 to track positions where an even number is expected.
2. An oddIndex starting at 1 to track positions where an odd number is expected. Iterate through the array:

• If the element at evenIndex is even, it’s in the correct position, so move to the next even index (evenIndex += 2).
• Similarly, if the element at oddIndex is odd, move to the next odd index (oddIndex += 2).
• If either position has an element of the wrong parity, swap the elements at evenIndex and oddIndex, and then move both pointers. This method ensures all elements are placed in the correct parity positions with a single pass through the array.

Code Solutions