Code Implementation

class Solution:
    def sortArrayByParityII(self, nums):
        n = len(nums)
        res = [0] * n
        even_idx, odd_idx = 0, 1
        for num in nums:
            if num % 2 == 0:
                res[even_idx] = num
                even_idx += 2
            else:
                res[odd_idx] = num
                odd_idx += 2
        return res
      

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        int even_idx = 0, odd_idx = 1;
        for (int num : nums) {
            if (num % 2 == 0) {
                res[even_idx] = num;
                even_idx += 2;
            } else {
                res[odd_idx] = num;
                odd_idx += 2;
            }
        }
        return res;
    }
};
      

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int evenIdx = 0, oddIdx = 1;
        for (int num : nums) {
            if (num % 2 == 0) {
                res[evenIdx] = num;
                evenIdx += 2;
            } else {
                res[oddIdx] = num;
                oddIdx += 2;
            }
        }
        return res;
    }
}
      

var sortArrayByParityII = function(nums) {
    const n = nums.length;
    const res = new Array(n);
    let evenIdx = 0, oddIdx = 1;
    for (let num of nums) {
        if (num % 2 === 0) {
            res[evenIdx] = num;
            evenIdx += 2;
        } else {
            res[oddIdx] = num;
            oddIdx += 2;
        }
    }
    return res;
};
      

Problem Description

Given an array nums consisting of even length (i.e., the array has 2N elements), where exactly half of the elements are even and the other half are odd, you must rearrange the array so that elements at even indices (0, 2, 4, ...) are even numbers, and elements at odd indices (1, 3, 5, ...) are odd numbers.

• You must return any valid solution that meets this requirement.
• Each element in nums must be used exactly once; do not reuse or discard any elements.
• Constraints: nums.length is even, and there are equal numbers of even and odd elements.

Thought Process

At first glance, this problem might seem to require checking every possible arrangement of the array to find one that matches the parity rule. However, because the input guarantees an equal number of even and odd numbers, and the output only needs any valid arrangement (not a sorted one), we can use a much more efficient approach.

The key realization is that we can place even numbers directly at even indices and odd numbers at odd indices as we scan through the input. This means we don't need to sort or swap unnecessarily, and we can construct a new result array in a single pass.

Instead of moving elements around in the original array (which can be tricky and error-prone), we'll use two pointers (one for even indices, one for odd) and fill a new array accordingly. This is both simple and efficient.

Solution Approach

• Step 1: Initialize a result array res of the same length as nums.
• Step 2: Set two pointers: even_idx starting at 0 (for even indices), and odd_idx starting at 1 (for odd indices).
• Step 3: Loop through each number in nums:
  • If the number is even (num % 2 == 0), place it at res[even_idx] and increment even_idx by 2.
  • If the number is odd, place it at res[odd_idx] and increment odd_idx by 2.
• Step 4: After the loop, res will have even numbers at even indices and odd numbers at odd indices, as required.
• Step 5: Return the result array.

This approach is efficient because it only requires a single pass through the input and uses constant extra pointers.

Example Walkthrough

Let's walk through an example with nums = [4, 2, 5, 7]:

1. Initialize res = [0, 0, 0, 0], even_idx = 0, odd_idx = 1.
2. First number is 4 (even): place at res[0] → res = [4, 0, 0, 0], even_idx = 2.
3. Next is 2 (even): place at res[2] → res = [4, 0, 2, 0], even_idx = 4.
4. Next is 5 (odd): place at res[1] → res = [4, 5, 2, 0], odd_idx = 3.
5. Next is 7 (odd): place at res[3] → res = [4, 5, 2, 7], odd_idx = 5.
6. Done! The result [4, 5, 2, 7] has even numbers at even indices and odd numbers at odd indices.

Note that other valid outputs (like [2, 7, 4, 5]) are also possible.

Time and Space Complexity

• Brute-force approach: Generating all permutations and checking them would take O(n!) time and O(n) space, which is infeasible for large arrays.
• Optimized approach (as above):
  • Time Complexity: O(n), because we scan the array once.
  • Space Complexity: O(n), since we build a new result array of the same size.
• If you are allowed to modify the input array in-place (Leetcode sometimes allows this), you could achieve O(1) extra space by swapping elements in-place using two pointers, but the above solution is simpler and meets the problem constraints.

Summary

The "Sort Array By Parity II" problem is efficiently solved by using two pointers to fill even and odd indices in a result array as we scan the input. This leverages the guarantee that the input contains an equal number of even and odd elements, allowing us to avoid sorting or brute-force permutations. The approach is simple, fast, and easy to implement, making it a great example of how understanding problem constraints can lead to elegant solutions.