Sort Array By Parity II

Problem Statement

You are provided with an array of integers named nums, where exactly half of the numbers are even, and the remaining half are odd. You need to reorganize this array in such a way that the odd indexed positions of the array contain odd numbers, and the even indexed positions contain even numbers. The primary challenge is to achieve this rearrangement and return any possible configuration of the array that meets this criterion.

Examples

Example 1

Input:

nums = [4,2,5,7]

Output:

[4,5,2,7]

Explanation:

[4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Example 2

Input:

nums = [2,3]

Output:

[2,3]

Constraints

• 2 <= nums.length <= 2 * 104
• nums.length is even.
• Half of the integers in nums are even.
• 0 <= nums[i] <= 1000

Approach and Intuition

The task is to arrange the numbers such that the parity of indices matches the parity of the numbers placed at those indices. The steps to achieve this are outlined below:

1. Identifying Even and Odd Numbers:

   • Traverse through the array and classify each number as even or odd.
   • Separate these into two different lists or arrays, one for even numbers and another for odd numbers.

2. Construct the Result Array:

   • Iterate through these two lists, placing even numbers at even indices and odd numbers at odd indices.
   • This can be efficiently managed by using two pointers, one pointing to the current fill position for even indices and the other for odd indices.

3. Efficient Checking and Placement:

   • As you progress through the original list, a check can be performed to decide whether the current number is even/odd and placed directly into the result list according to the index.
   • Adjustment of pointers ensures that each number goes into an appropriate index, either incrementing the even pointer or the odd pointer after placing each number.

4. Return the Result:

   • Since the resulting array must only follow the rule of even/odd pattern having been observed as detailed in the problem, any satisfactory arrangement can be considered a valid answer.
   • As shown in the examples, multiple correct answers are possible, and any accurate configuration can be returned.

Given the constraint that exactly half of the numbers are even, this approach will be both effective and efficient in achieving the desired outcome. The specific example illustrations testify to the potential variations in the arrangement that all achieve the appropriately distributed pattern. This method ensures that all possibilities comply with the input constraints.

Solutions

class Solution {
    public int[] rearrangeEvenOdd(int[] array) {
        int oddIndex = 1;
        for (int evenIndex = 0; evenIndex < array.length; evenIndex += 2)
            if (array[evenIndex] % 2 != 0) {
                while (array[oddIndex] % 2 != 0)
                    oddIndex += 2;
    
                // Perform the swap operation
                int swapTemp = array[evenIndex];
                array[evenIndex] = array[oddIndex];
                array[oddIndex] = swapTemp;
            }
    
        return array;
    }
}