# Sort Array By Parity II
**Difficulty:** EASY
[External](https://leetcode.com/problems/sort-array-by-parity-ii)
Canonical: https://scaleengineer.com/dsa/problems/sort-array-by-parity-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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_.

**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`

**Follow Up:** Could you solve it in-place?

# Approaches
## Using an Auxiliary Array
A straightforward approach is to use an additional array to store the sorted elements. We can iterate through the input array, and based on the parity of each number, place it in the correct position in the new array.
**Time:** O(N), where `N` is the number of elements in the array. We perform a single pass through the input array. · **Space:** O(N), as we use an auxiliary array of size `N` to store the result.
**Pros:** The logic is simple and easy to follow.; Implementation is straightforward.
**Cons:** It's not an in-place solution and requires extra memory, which can be a drawback for very large inputs.
### Explanation
We can solve this problem by allocating a new array, `result`, of the same size as the input `nums`. We'll use two index pointers: `evenIndex` starting at 0 for placing even numbers, and `oddIndex` starting at 1 for placing odd numbers.
We then iterate through each number in the input array `nums`.
- If the number is even, we place it at `result[evenIndex]` and then increment `evenIndex` by 2.
- If the number is odd, we place it at `result[oddIndex]` and then increment `oddIndex` by 2.
After iterating through all the numbers in `nums`, the `result` array will be sorted according to the problem's criteria.
```java
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int evenIndex = 0;
        int oddIndex = 1;
        for (int num : nums) {
            if (num % 2 == 0) {
                result[evenIndex] = num;
                evenIndex += 2;
            } else {
                result[oddIndex] = num;
                oddIndex += 2;
            }
        }
        return result;
    }
}
```
### Algorithm
- Create a new integer array `result` with the same length as `nums`.
- Initialize an `evenIndex` pointer to `0`.
- Initialize an `oddIndex` pointer to `1`.
- Iterate through each `num` in the input array `nums`.
- If `num` is even (i.e., `num % 2 == 0`), assign `result[evenIndex] = num` and update `evenIndex = evenIndex + 2`.
- If `num` is odd, assign `result[oddIndex] = num` and update `oddIndex = oddIndex + 2`.
- After the loop finishes, return the `result` array.

## In-place Swapping with Two Pointers
To solve the problem in-place as suggested by the follow-up, we can use a two-pointer technique. One pointer, `even`, will iterate through the even indices, and another pointer, `odd`, will iterate through the odd indices. The goal is to find and swap misplaced elements.
**Time:** O(N), where `N` is the number of elements. Although there are nested loops, each pointer (`even` and `odd`) traverses its respective set of indices (even or odd) at most once. Therefore, each element is visited a constant number of times. · **Space:** O(1). The sorting is performed in-place, so no additional space proportional to the input size is required.
**Pros:** Highly efficient in terms of space, satisfying the in-place requirement.; Maintains a linear time complexity.
**Cons:** The logic with two pointers and nested loops can be slightly more complex to reason about compared to the auxiliary array method.
### Explanation
This approach modifies the array directly without using extra space. We use two pointers: `even` starting at index 0 and `odd` starting at index 1.
The `even` pointer's job is to find the first even index `i` that holds an odd number (`nums[i] % 2 != 0`). It does this by advancing by 2 in each step (`even += 2`).
Similarly, the `odd` pointer's job is to find the first odd index `j` that holds an even number (`nums[j] % 2 == 0`). It also advances by 2 in each step (`odd += 2`).
Once both pointers have found a misplaced number, we swap `nums[even]` and `nums[odd]`. This places the even number at an even index and the odd number at an odd index, correcting their positions.
We repeat this process until either pointer goes beyond the array's bounds. Since the input is guaranteed to have an equal number of even and odd numbers, this process will correctly sort the entire array.
```java
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int even = 0;
        int odd = 1;
        
        while (even < n && odd < n) {
            // Find the first even index with an odd number
            while (even < n && nums[even] % 2 == 0) {
                even += 2;
            }
            
            // Find the first odd index with an even number
            while (odd < n && nums[odd] % 2 != 0) {
                odd += 2;
            }
            
            // If both pointers are valid, swap the elements
            if (even < n && odd < n) {
                int temp = nums[even];
                nums[even] = nums[odd];
                nums[odd] = temp;
            }
        }
        
        return nums;
    }
}
```
### Algorithm
- Initialize a pointer `even` to `0` and a pointer `odd` to `1`.
- Enter a loop that continues as long as both `even` and `odd` are within the array bounds (`< nums.length`).
- Inside the loop, advance the `even` pointer by 2 until it points to an odd number (`nums[even] % 2 != 0`) or goes out of bounds.
- Similarly, advance the `odd` pointer by 2 until it points to an even number (`nums[odd] % 2 == 0`) or goes out of bounds.
- If both pointers are still within the array bounds, it means we've found an odd number at an even index and an even number at an odd index. Swap `nums[even]` and `nums[odd]`.
- The loop continues until one of the pointers moves past the end of the array, at which point the array is correctly sorted.
- Return the modified `nums` array.

# Solutions
### Java

```java
class Solution {
public
  int[] sortArrayByParityII(int[] nums) {
    for (int i = 0, j = 1; i < nums.length; i += 2) {
      if ((nums[i] & 1) == 1) {
        while ((nums[j] & 1) == 1) {
          j += 2;
        }
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
      }
    }
    return nums;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[]} */ var sortArrayByParityII =
  function (nums) {
    for (let i = 0, j = 1; i < nums.length; i += 2) {
      if ((nums[i] & 1) == 1) {
        while ((nums[j] & 1) == 1) {
          j += 2;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
      }
    }
    return nums;
  };

```

### CPP

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

```

### Python

```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] & 1) == 1: while (nums[j] & 1) == 1: j += 2 nums[i], nums[j] = nums[j], nums[i] return nums

```