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.

Examples

Example 1

1
2
3

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

1
2

Input: nums = [2,3]
Output: [2,3]

Constraints

  • 2 <= nums.length <= 2 * 10^4
  • nums.length is even.
  • Half of the integers in nums are even.
  • 0 <= nums[i] <= 1000

Follow Up: Could you solve it in-place?

Solution

Method 1 - Two-Pass Solution (Separate Even and Odd)

Intuition

Separate even and odd numbers into different arrays, then place them alternately in the result array.

Approach

  1. Separate all even and odd numbers into different arrays
  2. Place even numbers at even indices (0, 2, 4, …)
  3. Place odd numbers at odd indices (1, 3, 5, …)
  4. Return the constructed result array

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the array
  • 🧺 Space complexity: O(n) for storing separate even and odd arrays

Code

 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

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        vector<int> even, odd;
        
        // Separate even and odd numbers
        for (int num : nums) {
            if (num % 2 == 0) {
                even.push_back(num);
            } else {
                odd.push_back(num);
            }
        }
        
        // Build result array
        vector<int> result(nums.size());
        int evenIdx = 0, oddIdx = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (i % 2 == 0) {
                result[i] = even[evenIdx++];
            } else {
                result[i] = odd[oddIdx++];
            }
        }
        
        return result;
    }
};
 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

func sortArrayByParityII(nums []int) []int {
    var even, odd []int
    
    // Separate even and odd numbers
    for _, num := range nums {
        if num%2 == 0 {
            even = append(even, num)
        } else {
            odd = append(odd, num)
        }
    }
    
    // Build result array
    result := make([]int, len(nums))
    evenIdx, oddIdx := 0, 0
    
    for i := 0; i < len(nums); i++ {
        if i%2 == 0 {
            result[i] = even[evenIdx]
            evenIdx++
        } else {
            result[i] = odd[oddIdx]
            oddIdx++
        }
    }
    
    return result
}
 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

import java.util.*;

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        List<Integer> even = new ArrayList<>();
        List<Integer> odd = new ArrayList<>();
        
        // Separate even and odd numbers
        for (int num : nums) {
            if (num % 2 == 0) {
                even.add(num);
            } else {
                odd.add(num);
            }
        }
        
        // Build result array
        int[] result = new int[nums.length];
        int evenIdx = 0, oddIdx = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                result[i] = even.get(evenIdx++);
            } else {
                result[i] = odd.get(oddIdx++);
            }
        }
        
        return result;
    }
}
 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

class Solution {
    fun sortArrayByParityII(nums: IntArray): IntArray {
        val even = mutableListOf<Int>()
        val odd = mutableListOf<Int>()
        
        // Separate even and odd numbers
        for (num in nums) {
            if (num % 2 == 0) {
                even.add(num)
            } else {
                odd.add(num)
            }
        }
        
        // Build result array
        val result = IntArray(nums.size)
        var evenIdx = 0
        var oddIdx = 0
        
        for (i in nums.indices) {
            if (i % 2 == 0) {
                result[i] = even[evenIdx++]
            } else {
                result[i] = odd[oddIdx++]
            }
        }
        
        return result
    }
}
 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

def sortArrayByParityII(nums: list[int]) -> list[int]:
    even = []
    odd = []
    
    # Separate even and odd numbers
    for num in nums:
        if num % 2 == 0:
            even.append(num)
        else:
            odd.append(num)
    
    # Build result array
    result = [0] * len(nums)
    even_idx = odd_idx = 0
    
    for i in range(len(nums)):
        if i % 2 == 0:
            result[i] = even[even_idx]
            even_idx += 1
        else:
            result[i] = odd[odd_idx]
            odd_idx += 1
    
    return result

# Alternative one-liner approach
def sortArrayByParityII2(nums: list[int]) -> list[int]:
    even = [x for x in nums if x % 2 == 0]
    odd = [x for x in nums if x % 2 == 1]
    
    result = []
    for i in range(len(nums) // 2):
        result.append(even[i])
        result.append(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
23
24
25
26
27
28
29
30
31
32

impl Solution {
    pub fn sort_array_by_parity_ii(nums: Vec<i32>) -> Vec<i32> {
        let mut even = Vec::new();
        let mut odd = Vec::new();
        
        // Separate even and odd numbers
        for num in &nums {
            if num % 2 == 0 {
                even.push(*num);
            } else {
                odd.push(*num);
            }
        }
        
        // Build result array
        let mut result = vec![0; nums.len()];
        let mut even_idx = 0;
        let mut odd_idx = 0;
        
        for i in 0..nums.len() {
            if i % 2 == 0 {
                result[i] = even[even_idx];
                even_idx += 1;
            } else {
                result[i] = odd[odd_idx];
                odd_idx += 1;
            }
        }
        
        result
    }
}
 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

function sortArrayByParityII(nums: number[]): number[] {
    const even: number[] = [];
    const odd: number[] = [];
    
    // Separate even and odd numbers
    for (const num of nums) {
        if (num % 2 === 0) {
            even.push(num);
        } else {
            odd.push(num);
        }
    }
    
    // Build result array
    const result: number[] = new Array(nums.length);
    let evenIdx = 0, oddIdx = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) {
            result[i] = even[evenIdx++];
        } else {
            result[i] = odd[oddIdx++];
        }
    }
    
    return result;
}

Method 2 - In-Place Two Pointers Solution

Intuition

Use two pointers to find misplaced elements and swap them to achieve the correct parity arrangement without extra space.

Approach

Approach

  1. Use one pointer for even indices and one for odd indices
  2. Find the first even index with an odd number
  3. Find the first odd index with an even number
  4. Swap these misplaced numbers
  5. Repeat until the array is correctly arranged

Code

 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

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int evenIdx = 0; // Points to even indices
        int oddIdx = 1;  // Points to odd indices
        
        while (evenIdx < nums.size() && oddIdx < nums.size()) {
            // Find misplaced even index (should have even number but has odd)
            while (evenIdx < nums.size() && nums[evenIdx] % 2 == 0) {
                evenIdx += 2;
            }
            
            // Find misplaced odd index (should have odd number but has even)
            while (oddIdx < nums.size() && nums[oddIdx] % 2 == 1) {
                oddIdx += 2;
            }
            
            // Swap misplaced elements if both found
            if (evenIdx < nums.size() && oddIdx < nums.size()) {
                swap(nums[evenIdx], nums[oddIdx]);
            }
        }
        
        return nums;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def sortArrayByParityII(nums: list[int]) -> list[int]:
    even_idx = 0  # Points to even indices
    odd_idx = 1   # Points to odd indices
    
    while even_idx < len(nums) and odd_idx < len(nums):
        # Find misplaced even index
        while even_idx < len(nums) and nums[even_idx] % 2 == 0:
            even_idx += 2
        
        # Find misplaced odd index
        while odd_idx < len(nums) and nums[odd_idx] % 2 == 1:
            odd_idx += 2
        
        # Swap misplaced elements if both found
        if even_idx < len(nums) and odd_idx < len(nums):
            nums[even_idx], nums[odd_idx] = nums[odd_idx], nums[even_idx]
    
    return nums

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the array
  • 🧺 Space complexity: O(1) for in-place solution