# LeetCode 922. Sort Array By Parity II

## Description

https://leetcode.com/problems/sort-array-by-parity-ii/

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?

## Explanation

Iterate the list and store the odd, even numbers separately. And then created a new empty list and based on indices to add odd, even numbers.

## Python Solution

``````class Solution:
def sortArrayByParityII(self, nums: List[int]) -> List[int]:
results = []

odds = []
evens = []
for num in nums:
if num % 2 == 0:
evens.append(num)
else:
odds.append(num)

i = 0
while i < len(nums):
if i % 2 == 0:
value = evens.pop(0)
else:
value = odds.pop(0)
results.append(value)

i += 1

return results``````
• Time Complexity: O(N).
• Space Complexity: O(N).