Sort Array By Parity II

Problem Description

Given an array of integers nums, half of the integers in nums are odd, and the other half are even. Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even. Return any answer array that satisfies this condition.

Key Insights

• The array contains an equal number of odd and even integers.
• The output array must alternate between even and odd integers based on their indices.
• The problem can be solved using a two-pointer technique to place even and odd numbers at their respective indices.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (in-place solution)

Solution

To solve the problem, we can use a two-pointer approach. We will maintain two separate pointers: one for the even indices and another for the odd indices. As we traverse the array, we will place even numbers at even indices and odd numbers at odd indices. This will ensure that the final array meets the requirements.

1. Initialize two pointers: one for the even index (i) starting at 0 and another for the odd index (j) starting at 1.
2. Iterate through the array:
   • If the current number is even and the current index is even, move the even pointer forward.
   • If the current number is odd and the current index is odd, move the odd pointer forward.
   • If the current number is at the wrong index (even number at an odd index or vice versa), swap it with the number at the correct index indicated by the respective pointer.
3. Continue this process until the entire array is sorted by parity.

Code Solutions