# LC 922. Sort Array By Parity II

### [Problem link](https://leetcode.com/problems/sort-array-by-parity-ii/)

###### tags: `leedcode` `python` `c++` `easy`

Given an array of integers <code>nums</code>, half of the integers in <code>nums</code> are **odd** , and the other half are **even** .

Sort the array so that whenever <code>nums[i]</code> is odd, <code>i</code> is **odd** , and whenever <code>nums[i]</code> is even, <code>i</code> 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:**

- <code>2 <= nums.length <= 2 * 10⁴</code>
- <code>nums.length</code> is even.
- Half of the integers in <code>nums</code> are even.
- <code>0 <= nums[i] <= 1000</code>

**Follow Up:** Could you solve it in-place?
## Solution 1
#### Python

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        n = len(nums)
        even_idx, odd_idx = 0, 1
        res = [0] * n

        for num in nums:
            if num % 2:
                res[odd_idx] = num
                odd_idx += 2
            else:
                res[even_idx] = num
                even_idx += 2

        return res

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int evenIdx = 0;
        int oddIdx = 1;
        
        vector<int> res(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] % 2) {
                res[oddIdx] = nums[i];
                oddIdx += 2;
            } else {
                res[evenIdx] = nums[i];
                evenIdx += 2;
            }
        }
        return res;
    }
};

## Soultion 2 - Follow Up
#### Python

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        n = len(nums)
        odd_idx = 1

        for i in range(0, n, 2):
            if nums[i] % 2:
                while nums[odd_idx] % 2:
                    odd_idx += 2
                nums[i], nums[odd_idx] = nums[odd_idx], nums[i]

        return nums

#### C++

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

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |
>| Solution 2 | O(n) | O(1) |

## Note
x