Sort Array By Parity II solution and explanation
Google
9 more videos on this problem
LeetCode Sort Array By Parity II Solution Explained - JavaNick White · 7:04 · 9K views
Leetcode - Sort Array By Parity II (Python)Timothy H Chang · 4:43 · 1K views
922 Sort Array By Parity II CPP SolutionAnimated Anand · 5:12 · 818 views
Leetcode 922 - Sort Array By Parity II (JAVA Solution Explained!)LC Bear · 5:59 · 455 views
922. Sort Array By Parity II ||LeetCodeSiddharth Nagaych · 7:24 · 419 views
922. Sort Array By Parity II || LEETCODE SOLUTION || IN C++ || DATA STRUCTURE AND ALGORITHMAbhishweta Gupta · 2:24 · 405 views
Java Solution | 922. Sort Array By Parity II | Two Pointer Easy O(n) | DSA Sheet by LearnYardCheatCode · 10:45 · 292 views
Leetcode 922.Sort Array By Parity-IIFriendly Neighborhood Coder · 6:08 · 272 views
Daily Leetcode #546: Sep 28, 2021 - 922. Sort Array By Parity IIProgramming Live with Larry · 12:41 · 220 views
Leetcode - 922 Sort Array By Parity II - PythonJake LeetCode · 3:34 · 157 views
The 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.
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 * 104nums.lengthis even.- Half of the integers in
numsare even. 0 <= nums[i] <= 1000
Follow Up: Could you solve it in-place?
Approach overview
Problem Overview: You receive an integer array where half the numbers are even and half are odd. Rearrange the array so that elements at even indices contain even numbers and elements at odd indices contain odd numbers.
Approach 1: Separate Arrays for Even and Odd Numbers (O(n) time, O(n) space)
This approach splits the array into two lists: one storing all even numbers and another storing all odd numbers. After collecting them, iterate through the original array and place values back such that even indices receive values from the even list and odd indices receive values from the odd list. The logic is straightforward and easy to reason about, making it a good starting point when you first see the problem. The trade‑off is extra memory because you store two additional arrays proportional to the input size. This method works well when clarity is more important than space efficiency and introduces the pattern of grouping values before reconstruction, a common technique in array manipulation problems.
Approach 2: Two Pointer Approach (O(n) time, O(1) space)
The optimal solution uses two pointers that jump across indices with the same parity. One pointer starts at index 0 and moves through even positions, while the other starts at index 1 and moves through odd positions. When the even pointer encounters an odd number and the odd pointer encounters an even number, swap them. Each pointer then advances by two positions. Because every element is examined at most once and swaps fix two incorrect placements simultaneously, the algorithm completes in linear time. This in-place technique avoids additional memory and demonstrates a classic two pointers strategy applied to index parity rather than array ends.
The key insight is that incorrect placements always occur in pairs: an odd number sitting in an even index must be matched with an even number sitting in an odd index. Swapping those two elements resolves both violations at once. The algorithm continues until both pointers reach the end of the array.
Although the problem can technically be solved by sorting or repeated searching for the correct parity element, those methods introduce unnecessary overhead compared to the direct pointer approach.
Recommended for interviews: The two pointer solution is what most interviewers expect. It runs in O(n) time and O(1) space while clearly demonstrating control over index traversal and in-place swapping. Mentioning the separate-arrays method first can show initial reasoning, but implementing the pointer-based approach signals stronger algorithmic thinking.
Approach 1: Two Pointer Approach
This approach utilizes two pointers to iteratively place even and odd numbers at the correct indexes.
One pointer is used to find even numbered indexes and the other one for odd numbered indexes. Traverse through the array, and whenever you find an element not in its correct place, swap it with the correct one using the two pointers.
class Solution:
def sortArrayByParityII(self, nums):
even, odd = 0, 1
n = len(nums)
while even < n and odd < n:
if nums[even] % 2 == 0:
even += 2
elif nums[odd] % 2 == 1:
odd += 2
else:
nums[even], nums[odd] = nums[odd], nums[even]
even += 2
odd += 2
return numsclass Solution {
public int[] sortArrayByParityII(int[] nums) {
int even = 0, odd = 1;
while (even < nums.length && odd < nums.length) {
while (even < nums.length && nums[even] % 2 == 0) even += 2;
while (odd < nums.length && nums[odd] % 2 == 1) odd += 2;
if (even < nums.length && odd < nums.length) {
int temp = nums[even];
nums[even] = nums[odd];
nums[odd] = temp;
}
}
return nums;
}
}class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& nums) {
int even = 0, odd = 1, n = nums.size();
while (even < n && odd < n) {
while (even < n && nums[even] % 2 == 0) even += 2;
while (odd < n && nums[odd] % 2 == 1) odd += 2;
if (even < n && odd < n) swap(nums[even], nums[odd]);
}
return nums;
}
};var sortArrayByParityII = function(nums) {
let even = 0, odd = 1, n = nums.length;
while (even < n && odd < n) {
while (even < n && nums[even] % 2 === 0) even += 2;
while (odd < n && nums[odd] % 2 === 1) odd += 2;
if (even < n && odd < n) {
[nums[even], nums[odd]] = [nums[odd], nums[even]];
}
}
return nums;
};#include <stdbool.h>
void sortArrayByParityII(int* nums, int numsSize) {
int even = 0, odd = 1;
while (even < numsSize && odd < numsSize) {
while (even < numsSize && nums[even] % 2 == 0) even += 2;
while (odd < numsSize && nums[odd] % 2 == 1) odd += 2;
if (even < numsSize && odd < numsSize) {
int temp = nums[even];
nums[even] = nums[odd];
nums[odd] = temp;
}
}
}public class Solution {
public int[] SortArrayByParityII(int[] nums) {
int even = 0, odd = 1, n = nums.Length;
while (even < n && odd < n) {
while (even < n && nums[even] % 2 == 0) even += 2;
while (odd < n && nums[odd] % 2 == 1) odd += 2;
if (even < n && odd < n) {
int temp = nums[even];
nums[even] = nums[odd];
nums[odd] = temp;
}
}
return nums;
}
}The Python approach is straightforward due to Python's flexible syntax.
The even and odd pointers leverage the % operator for checking parity and swap out-of-place numbers.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Separate Arrays for Even and Odd Numbers
This approach involves segregating even and odd numbers into separate lists and then efficiently assembling them at respected places in the resultant array.
Despite potentially not being in-place, this technique simplifies understanding the array content and meets the problem requirements.
class Solution:
def sortArrayByParityII(self, nums):
evens = [x for x in nums if x % 2 == 0]
odds = [x for x in nums if x % 2 == 1]
result = [0] * len(nums)
result[::2] = evens
result[1::2] = odds
return resultvar sortArrayByParityII = function(nums) {
let evens = nums.filter(num => num % 2 === 0);
let odds = nums.filter(num => num % 2 === 1);
let result = [];
for (let i = 0; i < evens.length; i++) {
result.push(evens[i]);
result.push(odds[i]);
}
return result;
};This Python method separates evens and odds into different sublists. Then it assembles those lists alternatively filling into the result array.
This approach straightforwardly constructs a properly sequenced result list.
Time Complexity: O(n)
Space Complexity: O(n) due to the auxiliary lists for even and odd numbers.
Approach 3: Two Pointers
We use two pointers i and j to point to even and odd indices, respectively. Initially, i = 0 and j = 1.
When i points to an even index, if nums[i] is odd, we need to find an odd index j such that nums[j] is even, and then swap nums[i] and nums[j]. Continue traversing until i reaches the end of the array.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function sortArrayByParityII(nums: number[]): number[] {
for (let i = 0, j = 1; i < nums.length; i += 2) {
if (nums[i] % 2) {
while (nums[j] % 2) {
j += 2;
}
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
return nums;
}func sortArrayByParityII(nums []int) []int {
for i, j := 0, 1; i < len(nums); i += 2 {
if nums[i]%2 == 1 {
for nums[j]%2 == 1 {
j += 2
}
nums[i], nums[j] = nums[j], nums[i]
}
}
return nums
}impl Solution {
pub fn sort_array_by_parity_ii(mut nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut j = 1;
for i in (0..n).step_by(2) {
if nums[i] % 2 != 0 {
while nums[j] % 2 != 0 {
j += 2;
}
nums.swap(i, j);
}
}
nums
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointer Approach | Time Complexity: O(n) |
| Separate Arrays for Even and Odd Numbers | Time Complexity: O(n) |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Separate Arrays for Even and Odd Numbers | O(n) | O(n) | When prioritizing clarity or when modifying the original array is not required |
| Two Pointer Approach (In‑Place) | O(n) | O(1) | Best choice for interviews and production due to constant space and simple swaps |
Frequently asked questions
Is Sort Array By Parity II easy or hard?
Sort Array By Parity II is classified as an Easy problem on LeetCode with an acceptance rate around 70%. It focuses on simple array traversal and pointer control rather than advanced data structures or complex algorithms.
Sort Array By Parity II Python/Java solution
Most implementations follow the two pointer strategy. In Python or Java, maintain two indices (0 and 1) and increment them by 2 while swapping misplaced elements. The logic remains identical across languages and runs in O(n) time with constant extra space.
How to solve Sort Array By Parity II in O(n)?
Use two pointers: one starting at index 0 for even positions and another at index 1 for odd positions. Move each pointer forward by two indices. When an even index contains an odd value and an odd index contains an even value, swap them. This corrects both positions in a single operation.
What is the best approach for Sort Array By Parity II?
The two pointer approach is the most efficient method. Use one pointer for even indices and another for odd indices, and swap elements whenever an index contains the wrong parity. This runs in O(n) time and O(1) space because the array is rearranged in place.
Is Sort Array By Parity II asked at Google/Amazon/Meta?
Parity-based array rearrangement problems appear frequently in interviews at large tech companies because they test basic array manipulation and pointer logic. Variants of this problem have appeared in interview preparation sets used for companies like Amazon, Google, and Meta.
What data structure is used in Sort Array By Parity II?
The problem primarily uses arrays with pointer-based traversal. The optimal solution relies on two index pointers to scan even and odd positions, while a simpler alternative may temporarily store values in separate arrays for even and odd numbers.
What is the time complexity of Sort Array By Parity II?
The optimal solution runs in O(n) time because each index is visited at most once while scanning even and odd positions. The space complexity is O(1) since the rearrangement is performed directly inside the input array.