Solution Explanation: Sort Array By Parity II

This problem asks us to sort an array such that even-indexed elements are even numbers and odd-indexed elements are odd numbers. The input array guarantees that exactly half of the elements are even and half are odd.

The most efficient approach is using a two-pointer technique. This avoids the overhead of full sorting algorithms like merge sort or quicksort which would have a time complexity of O(n log n).

Approach: Two Pointers

1. Initialization: We use two pointers, i and j. i starts at index 0 (the first even index) and increments by 2 in each iteration, processing even indices. j starts at index 1 (the first odd index) and also increments by 2, processing odd indices.

2. Iteration: The outer loop iterates through even indices (i). Inside the loop, we check if the element at nums[i] is odd (nums[i] % 2 != 0).

3. Swapping: If nums[i] is odd, we need to find an even number to swap with it. The inner loop iterates through odd indices (j) until it finds an even number (nums[j] % 2 == 0). Once an even number is found at nums[j], we swap nums[i] and nums[j].

4. Continuation: The outer loop continues, processing the next even index. The inner loop only searches for an even number when needed, reducing unnecessary iterations.

Time and Space Complexity

• Time Complexity: O(n) - In the worst case, we might iterate through almost all elements once (when many odd numbers are in even positions). The inner loop only executes when necessary, and even then it doesn't re-scan already checked portions of the array.

• Space Complexity: O(1) - The algorithm operates in-place; we use only a few variables for pointers, not additional data structures proportional to the input size.

Code Examples (Multiple Languages)

The code implementations below demonstrate the two-pointer approach in several programming languages. They all follow the same logic outlined above.

Python:

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        n, j = len(nums), 1
        for i in range(0, n, 2):
            if nums[i] % 2:  # Check if nums[i] is odd
                while nums[j] % 2: # Find an even number at odd index
                    j += 2
                nums[i], nums[j] = nums[j], nums[i] # Swap
        return nums

Java:

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        for (int i = 0, j = 1; i < n; i += 2) {
            if (nums[i] % 2 != 0) {
                while (nums[j] % 2 != 0) {
                    j += 2;
                }
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        return nums;
    }
}

C++:

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0, j = 1; i < n; i += 2) {
            if (nums[i] % 2 != 0) {
                while (nums[j] % 2 != 0) {
                    j += 2;
                }
                swap(nums[i], nums[j]);
            }
        }
        return nums;
    }
};

JavaScript:

var sortArrayByParityII = function(nums) {
    let n = nums.length;
    for (let i = 0, j = 1; i < n; i += 2) {
        if (nums[i] % 2 !== 0) {
            while (nums[j] % 2 !== 0) {
                j += 2;
            }
            [nums[i], nums[j]] = [nums[j], nums[i]]; //Swap using destructuring
        }
    }
    return nums;
};

These examples highlight the core algorithm. Adaptations for other languages will be very similar in structure and efficiency. The key is the efficient use of two pointers to achieve linear time complexity.