# 922. Sort Array By Parity II

LeetCode Problem Link (opens new window)

Given a non-negative integer array nums, where half of the integers are odd, and half of the integers are even.

Sort the array so that when nums[i] is odd, i is also odd; and when nums[i] is even, i is also even.

You may return any array that satisfies the above conditions as the answer.

Example:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], and [2,7,4,5] would also be accepted.

# Approach

A straightforward method might be using two layers of for loops plus a used array to indicate utilized elements. This would result in a time complexity of O(n^2).

# Method 1

In fact, this problem can be solved using a more straightforward method with a time complexity of O(n). Here is the C++ code:

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        vector<int> even(nums.size() / 2); // Initialize to specify array size to save overhead
        vector<int> odd(nums.size() / 2);
        vector<int> result(nums.size());
        int evenIndex = 0;
        int oddIndex = 0;
        int resultIndex = 0;
        // Place `nums` array into even and odd arrays
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] % 2 == 0) even[evenIndex++] = nums[i];
            else odd[oddIndex++] = nums[i];
        }
        // Put even and odd arrays back into the result array
        for (int i = 0; i < evenIndex; i++) {
            result[resultIndex++] = even[i];
            result[resultIndex++] = odd[i];
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Time Complexity: O(n)
Space Complexity: O(n)

# Method 2

The code above uses two auxiliary arrays, and the nums array is effectively traversed twice. The advantage of using auxiliary arrays is clarity. An optimized version without auxiliary arrays is shown below:

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        vector<int> result(nums.size());
        int evenIndex = 0;  // Index for even numbers
        int oddIndex = 1;   // Index for odd numbers
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] % 2 == 0) {
                result[evenIndex] = nums[i];
                evenIndex += 2;
            }
            else {
                result[oddIndex] = nums[i];
                oddIndex += 2;
            }
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Time Complexity: O(n)
Space Complexity: O(n)

# Method 3

Of course, this can also be done in place in the original array without even needing the result array.

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int oddIndex = 1;
        for (int i = 0; i < nums.size(); i += 2) {
            if (nums[i] % 2 == 1) { // Encountered odd number at even position
                while(nums[oddIndex] % 2 != 0) oddIndex += 2; // Find an even number at an odd position
                swap(nums[i], nums[oddIndex]); // Swap
            }
        }
        return nums;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

Time Complexity: O(n)
Space Complexity: O(1)

The time complexity here is not O(n^2) because each element in both even and odd positions is operated upon only once, making it n/2 + n/2, not n/2 * n/2!

# Versions in Other Languages

# Java

// Method 1
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        // Store the odd and even numbers from nums
        int len = nums.length;
        int evenIndex = 0;
        int oddIndex = 0;
        int[] even = new int[len / 2];
        int[] odd = new int[len / 2];
        for (int i = 0; i < len; i++) {
            if (nums[i] % 2 == 0) {
                even[evenIndex++] = nums[i];
            } else {
                odd[oddIndex++] = nums[i];
            }
        }
        // Store the odd and even arrays back in nums
        int index = 0;
        for (int i = 0; i < even.length; i++) {
            nums[index++] = even[i];
            nums[index++] = odd[i];
        }
        return nums;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Method 1: Using extra array space
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        // Define result array
        int[] result = new int[nums.length];
        int even = 0, odd = 1;
        for(int i = 0; i < nums.length; i++){
            // If it's even
            if(nums[i] % 2 == 0){
                result[even] = nums[i];
                even += 2;
            }else{
                result[odd] = nums[i];
                odd += 2;
            }
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// Method 2: Not using extra array space
class Solution922 {
    public int[] sortArrayByParityII(int[] nums) {
        // Define two pointers
        int oddPoint = 1, evenPoint = 0;
        // Start moving and swapping, with the last layer inevitably swapping and then moving, or moving if they’re the same
        while(oddPoint < nums.length && evenPoint < nums.length){
            if(nums[oddPoint] % 2 == 0 && nums[evenPoint] % 2 == 1){
                int temp = 0;
                temp = nums[oddPoint];
                nums[oddPoint] = nums[evenPoint];
                nums[evenPoint] = temp;
                oddPoint += 2;
                evenPoint += 2;
            }else if(nums[oddPoint] % 2 == 0 && nums[evenPoint] % 2 == 0){
                evenPoint += 2;
            }else if(nums[oddPoint] % 2 == 1 && nums[evenPoint] % 2 == 1){
                oddPoint += 2;
            }else{
                oddPoint += 2;
                evenPoint += 2;
            }
        }
        return nums;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# Python3

# Method 2
class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        result = [0]*len(nums)
        evenIndex = 0
        oddIndex = 1
        for i in range(len(nums)):
            if nums[i] % 2: # Odd
                result[oddIndex] = nums[i]
                oddIndex += 2
            else: # Even
                result[evenIndex] = nums[i]
                evenIndex += 2
        return result

# Method 3
class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        oddIndex = 1
        for i in range(0,len(nums),2): # Step size 2
            if nums[i] % 2: # Odd number at an even position
                while nums[oddIndex] % 2: # Find even number at odd position
                    oddIndex += 2
                nums[i], nums[oddIndex] = nums[oddIndex], nums[i]
        return nums

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Go

// Method 1
func sortArrayByParityII(nums []int) []int {
	even, odd := []int{}, []int{}
	for i := 0; i < len(nums); i++ {
		if (nums[i] % 2 == 0) {
			even = append(even, nums[i])
		} else {
			odd = append(odd, nums[i])
		}
	}

	result := make([]int, len(nums))
	index := 0
	for i := 0; i < len(even); i++ {
		result[index] = even[i]; index++;
		result[index] = odd[i]; index++;
	}
	return result;
}

// Method 2
func sortArrayByParityII(nums []int) []int {
    result := make([]int, len(nums))
    evenIndex := 0
    oddIndex := 1
    for _, v := range nums {
        if v % 2 == 0 {
            result[evenIndex] = v
            evenIndex += 2
        } else {
            result[oddIndex] = v
            oddIndex += 2
        }
    }
    return result
}

// Method 3
func sortArrayByParityII(nums []int) []int {
    oddIndex := 1
    for i := 0; i < len(nums); i += 2 {
        if nums[i] % 2 == 1 {
            for nums[oddIndex] % 2 != 0 {
                oddIndex += 2 
            }
            nums[i], nums[oddIndex] = nums[oddIndex], nums[i]
        }
    }
    return nums
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# JavaScript

// Method 1
var sortArrayByParityII = function(nums) {
    const n = nums.length;
    let evenIndex = 0, oddIndex = 0;
    const even = new Array(Math.floor(n/2));
    const odd = new Array(Math.floor(n/2));
    for(let i = 0; i < n; i++){
        if(nums[i] % 2 === 0) even[evenIndex++] = nums[i];
        else odd[oddIndex++] = nums[i];
    }
    let index = 0;
    for(let i = 0; i < even.length; i++){
        nums[index++] = even[i];
        nums[index++] = odd[i];
    }
    return nums;
};

// Method 2
var sortArrayByParityII = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    let evenIndex = 0, oddIndex = 1;
    for(let i = 0; i < n; i++){
        if(nums[i] % 2 === 0) {
            result[evenIndex] = nums[i];
            evenIndex += 2;
        } else {
            result[oddIndex] = nums[i];
            oddIndex += 2;
        }
    }
    return result;
};

// Method 3
var sortArrayByParityII = function(nums) {
    let oddIndex = 1;
    for(let i = 0; i < nums.length; i += 2){
        if(nums[i] % 2 === 1){
            while(nums[oddIndex] % 2 !== 0) oddIndex += 2;
            [nums[oddIndex], nums[i]] = [nums[i], nums[oddIndex]];
        }
    }
    return nums;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

# TypeScript

Method 1:

function sortArrayByParityII(nums: number[]): number[] {
    const evenArr: number[] = [],
        oddArr: number[] = [];
    for (let num of nums) {
        if (num % 2 === 0) {
            evenArr.push(num);
        } else {
            oddArr.push(num);
        }
    }
    const resArr: number[] = [];
    for (let i = 0, length = nums.length / 2; i < length; i++) {
        resArr.push(evenArr[i]);
        resArr.push(oddArr[i]);
    }
    return resArr;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Method 2:

function sortArrayByParityII(nums: number[]): number[] {
    const length: number = nums.length;
    const resArr: number[] = [];
    let evenIndex: number = 0,
        oddIndex: number = 1;
    for (let i = 0; i < length; i++) {
        if (nums[i] % 2 === 0) {
            resArr[evenIndex] = nums[i];
            evenIndex += 2;
        } else {
            resArr[oddIndex] = nums[i];
            oddIndex += 2;
        }
    }
    return resArr;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Method 3:

function sortArrayByParityII(nums: number[]): number[] {
    const length: number = nums.length;
    let oddIndex: number = 1;
    for (let evenIndex = 0; evenIndex < length; evenIndex += 2) {
        if (nums[evenIndex] % 2 === 1) {
            while (oddIndex < length && nums[oddIndex] % 2 === 1) {
                oddIndex += 2;
            }
            let temp = nums[evenIndex];
            nums[evenIndex] = nums[oddIndex];
            nums[oddIndex] = temp;
        }
    }
    return nums;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15