Sort Array By Parity II

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

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

Separate all even and odd numbers into different arrays
Place even numbers at even indices (0, 2, 4, ...)
Place odd numbers at odd indices (1, 3, 5, ...)
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

C++

#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;
    }
};

Go

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
}

Java

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;
    }
}

Kotlin

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
    }
}

Python

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

Rust

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
    }
}

TypeScript

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

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

Code

C++

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;
    }
};

Java

import java.util.*;

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int evenIdx = 0; // points to even indices
        int oddIdx = 1;  // points to odd indices

        while (evenIdx < nums.length && oddIdx < nums.length) {
            // find misplaced even index (has odd number)
            while (evenIdx < nums.length && nums[evenIdx] % 2 == 0) {
                evenIdx += 2;
            }
            // find misplaced odd index (has even number)
            while (oddIdx < nums.length && nums[oddIdx] % 2 == 1) {
                oddIdx += 2;
            }
            if (evenIdx < nums.length && oddIdx < nums.length) {
                int tmp = nums[evenIdx];
                nums[evenIdx] = nums[oddIdx];
                nums[oddIdx] = tmp;
            }
        }
        return nums;
    }
}

Python

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

Problem

Examples

Example 1

Example 2

Constraints

Solution

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

Intuition

Approach

Complexity

Code

C++

Go

Java

Kotlin

Python

Rust

TypeScript

Method 2 - In-Place Two Pointers Solution

Intuition

Approach

Approach

Code

C++

Java

Python

Complexity

Comments