Sort Array By Parity solution and explanation
Google
TCS
9 more videos on this problem
Sort Array by Parity - Leetcode 905 - PythonNeetCodeIO · 7:25 · 11K views
Sort Array By Parity | LeetCode 905 | C++, Java, PythonKnowledge Center · 7:49 · 3K views
Sort Array By Parity | Leetcode - 905Algorithms Made Easy · 3:48 · 787 views
Sort Array By Parity - LeetCode #905 | Python, JavaScript, Java, C++CodingNinja · 4:26 · 696 views
LeetCode - 905. Sort Array By Parity | Arrays CardAditya Mahajan · 8:18 · 682 views
Sort Array By Parity | Leet code 905 | Theory explained + Python codeSai Anish Malla · 6:01 · 617 views
Master the Art of Array Sorting LeetCode 905. Sort Array By Parity SolutionsvanAmsen · 5:53 · 583 views
Leetcode : 905. Sort Array By Parity || JavaTKGgames · 12:44 · 557 views
905. Sort Array By Parity | LEETCODE EASYcode Explainer · 6:09 · 312 views
LeetCode Problem 905: Sort Array By Parity (Java)Seven Algorithms · 6:46 · 223 views
The problem
Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.
Return any array that satisfies this condition.
Example 1:
Input: nums = [3,1,2,4] Output: [2,4,3,1] Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
Example 2:
Input: nums = [0] Output: [0]
Constraints:
1 <= nums.length <= 50000 <= nums[i] <= 5000
Approach overview
Problem Overview: You receive an integer array and must reorder it so that all even numbers appear before all odd numbers. The relative order does not matter. Any valid arrangement where every even value comes before every odd value is accepted.
Approach 1: Two-Pointer Technique (O(n) time, O(1) space)
This approach treats the array like a partitioning problem. Use two pointers: one starting from the left and one from the right. The left pointer searches for an odd number that is misplaced, while the right pointer searches for an even number that should move forward. When both conditions are met, swap the elements and move both pointers inward. Each element is inspected at most once, which keeps the runtime linear. This in-place strategy is memory efficient and mirrors the partition logic used in quicksort-style problems. It is a common pattern when working with two pointers on an array.
The key insight is that you do not need full sorting. The task only requires grouping elements by parity. By continuously correcting misplaced elements from both ends, the array gradually forms two partitions: evens on the left and odds on the right. Because swaps occur directly inside the original array, no extra memory is required.
Approach 2: Separate and Concatenate (O(n) time, O(n) space)
This method builds two temporary lists while iterating through the array once. During the iteration, check each element with num % 2. Append even numbers to one list and odd numbers to another. After the pass completes, concatenate the even list with the odd list to produce the final result. The logic is straightforward and easy to implement, making it a good baseline solution when clarity matters more than memory usage.
The tradeoff is extra space. Since two auxiliary lists are created, the space complexity grows linearly with the input size. However, the runtime remains O(n) because each element is processed once. Conceptually, this approach resembles a simplified grouping step often used before sorting or partitioning operations.
Recommended for interviews: The two-pointer technique is the solution most interviewers expect. It demonstrates that you recognize this as a partition problem and can solve it in-place with O(n) time and O(1) space. The separate-and-concatenate approach still shows correct reasoning and linear processing, but the additional memory makes it less optimal.
Approach 1: Approach 1: Two-Pointer Technique
The two-pointer technique is useful to place even numbers at the beginning and odd numbers at the end in an in-place manner. We start with two pointers, one at the beginning and the other at the end of the array. If the element at the start is even, move the start pointer forward. If the element at the end is odd, move the end pointer backward. Whenever we find an odd number at the start pointer and an even number at the end pointer, we swap them. Continue this process until the two pointers meet.
def sortArrayByParity(nums):
i, j = 0, len(nums) - 1
while i < j:
if nums[i] % 2 > nums[j] % 2:
nums[i], nums[j] = nums[j], nums[i]
if nums[i] % 2 == 0: i += 1
if nums[j] % 2 == 1: j -= 1
return nums
nums = [3, 1, 2, 4]
sorted_nums = sortArrayByParity(nums)
print(sorted_nums)import java.util.Arrays;
public class SortArrayByParity {
public static void sortArrayByParity(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
if (nums[i] % 2 > nums[j] % 2) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
if (nums[i] % 2 == 0) i++;
if (nums[j] % 2 == 1) j--;
}
}
public static void main(String[] args) {
int[] nums = {3, 1, 2, 4};
sortArrayByParity(nums);
System.out.println(Arrays.toString(nums));
}
}#include <iostream>
#include <vector>
void sortArrayByParity(std::vector<int>& nums) {
int i = 0, j = nums.size() - 1;
while (i < j) {
if (nums[i] % 2 > nums[j] % 2) {
std::swap(nums[i], nums[j]);
}
if (nums[i] % 2 == 0) i++;
if (nums[j] % 2 == 1) j--;
}
}
int main() {
std::vector<int> nums = {3, 1, 2, 4};
sortArrayByParity(nums);
for (int num : nums) {
std::cout << num << " ";
}
return 0;
}function sortArrayByParity(nums) {
let i = 0, j = nums.length - 1;
while (i < j) {
if (nums[i] % 2 > nums[j] % 2) [nums[i], nums[j]] = [nums[j], nums[i]];
if (nums[i] % 2 === 0) i++;
if (nums[j] % 2 === 1) j--;
}
return nums;
}
let nums = [3, 1, 2, 4];
console.log(sortArrayByParity(nums));#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void sortArrayByParity(int* nums, int numsSize) {
int i = 0, j = numsSize - 1;
while (i < j) {
if (nums[i] % 2 > nums[j] % 2) {
swap(&nums[i], &nums[j]);
}
if (nums[i] % 2 == 0) i++;
if (nums[j] % 2 == 1) j--;
}
}
int main() {
int nums[] = {3, 1, 2, 4};
int size = sizeof(nums) / sizeof(nums[0]);
sortArrayByParity(nums, size);
for (int i = 0; i < size; i++) {
printf("%d ", nums[i]);
}
return 0;
}using System;
class SortArrayByParity {
public static void SortArrayByParityMethod(int[] nums) {
int i = 0, j = nums.Length - 1;
while (i < j) {
if (nums[i] % 2 > nums[j] % 2) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
if (nums[i] % 2 == 0) i++;
if (nums[j] % 2 == 1) j--;
}
}
static void Main() {
int[] nums = {3, 1, 2, 4};
SortArrayByParityMethod(nums);
Console.WriteLine(string.Join(", ", nums));
}
}This Python code sorts the array in place by moving even numbers to the front and odd numbers to the back using two pointers.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Approach 2: Separate and Concatenate
This approach involves creating two separate lists: one for even numbers and one for odd numbers. We traverse the original array and append every even number to the even list and every odd number to the odd list. Finally, concatenate the even list with the odd list to form the result.
def sortArrayByParity(nums):
evens = []
odds = []
for num in nums:
if num % 2 == 0:
evens.append(num)
else:
odds.append(num)
return evens + odds
nums = [3, 1, 2, 4]
print(sortArrayByParity(nums))import java.util.ArrayList;
import java.util.List;
public class SortArrayByParity {
public static int[] sortArrayByParity(int[] nums) {
int[] result = new int[nums.length];
int evenIndex = 0, oddIndex = nums.length - 1;
for (int num : nums) {
if (num % 2 == 0) result[evenIndex++] = num;
else result[oddIndex--] = num;
}
return result;
}
public static void main(String[] args) {
int[] nums = {3, 1, 2, 4};
int[] sorted = sortArrayByParity(nums);
for (int num : sorted) {
System.out.print(num + " ");
}
}
}#include <iostream>
#include <vector>
std::vector<int> sortArrayByParity(std::vector<int>& nums) {
std::vector<int> result(nums.size());
int evenIndex = 0, oddIndex = nums.size() - 1;
for (int num : nums) {
if (num % 2 == 0) result[evenIndex++] = num;
else result[oddIndex--] = num;
}
return result;
}
int main() {
std::vector<int> nums = {3, 1, 2, 4};
std::vector<int> sorted = sortArrayByParity(nums);
for (int num : sorted) {
std::cout << num << " ";
}
return 0;
}function sortArrayByParity(nums) {
let evens = [];
let odds = [];
for (let num of nums) {
if (num % 2 === 0) evens.push(num);
else odds.push(num);
}
return [...evens, ...odds];
}
let nums = [3, 1, 2, 4];
console.log(sortArrayByParity(nums));#include <stdio.h>
#include <stdlib.h>
int* sortArrayByParity(int* nums, int numsSize, int* returnSize) {
int* result = (int*)malloc(numsSize * sizeof(int));
int evenIndex = 0, oddIndex = numsSize - 1;
for (int i = 0; i < numsSize; i++) {
if (nums[i] % 2 == 0) {
result[evenIndex++] = nums[i];
} else {
result[oddIndex--] = nums[i];
}
}
*returnSize = numsSize;
return result;
}
int main() {
int nums[] = {3, 1, 2, 4};
int size = sizeof(nums) / sizeof(nums[0]);
int returnSize;
int* sorted = sortArrayByParity(nums, size, &returnSize);
for (int i = 0; i < size; i++) {
printf("%d ", sorted[i]);
}
free(sorted);
return 0;
}using System;
using System.Collections.Generic;
class SortArrayByParity {
public static int[] SortArrayByParityMethod(int[] nums) {
List<int> evens = new List<int>();
List<int> odds = new List<int>();
foreach (int num in nums) {
if (num % 2 == 0) evens.Add(num);
else odds.Add(num);
}
evens.AddRange(odds);
return evens.ToArray();
}
static void Main() {
int[] nums = {3, 1, 2, 4};
int[] sorted = SortArrayByParityMethod(nums);
Console.WriteLine(string.Join(", ", sorted));
}
}The Python version accumulates even and odd elements into separate lists before concatenating them back.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Two Pointers
We use two pointers i and j to point to the beginning and end of the array respectively. When i < j, we perform the following operations.
- If
nums[i]is even, then incrementiby1. - If
nums[j]is odd, then decrementjby1. - If
nums[i]is odd andnums[j]is even, then swapnums[i]andnums[j]. Then incrementiby1, and decrementjby1.
Finally, return the array nums.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function sortArrayByParity(nums: number[]): number[] {
for (let i = 0, j = nums.length - 1; i < j; ) {
if (nums[i] % 2 === 0) {
++i;
} else if (nums[j] % 2 === 1) {
--j;
} else {
[nums[i], nums[j]] = [nums[j], nums[i]];
++i;
--j;
}
}
return nums;
}func sortArrayByParity(nums []int) []int {
for i, j := 0, len(nums)-1; i < j; {
if nums[i]%2 == 0 {
i++
} else if nums[j]%2 == 1 {
j--
} else {
nums[i], nums[j] = nums[j], nums[i]
}
}
return nums
}impl Solution {
pub fn sort_array_by_parity(mut nums: Vec<i32>) -> Vec<i32> {
let (mut i, mut j) = (0, nums.len() - 1);
while i < j {
if nums[i] % 2 == 0 {
i += 1;
} else if nums[j] % 2 == 1 {
j -= 1;
} else {
nums.swap(i, j);
i += 1;
j -= 1;
}
}
nums
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Technique | Time Complexity: O(n) |
| Approach 2: Separate and Concatenate | Time Complexity: O(n) |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(1) | Best general solution when in-place modification is allowed and minimal memory usage is preferred. |
| Separate and Concatenate | O(n) | O(n) | Good for readability or functional-style implementations where creating new arrays is acceptable. |
Frequently asked questions
Is Sort Array By Parity easy or hard?
Sort Array By Parity is classified as an Easy problem. The main concept is recognizing that full sorting is unnecessary and that a simple partition using two pointers can solve it in linear time.
Sort Array By Parity Python/Java solution
In Python or Java, iterate using two indices and swap elements when an odd number appears on the left and an even number appears on the right. The same logic works in C++, C#, and JavaScript with identical O(n) time and O(1) space complexity.
How to solve Sort Array By Parity in O(n)?
Traverse the array with two pointers. Move the left pointer until it finds an odd number and move the right pointer until it finds an even number. Swap them and continue until the pointers cross. This partitions the array in a single linear pass.
What is the best approach for Sort Array By Parity?
The two-pointer technique is the most efficient approach. Use one pointer from the start and another from the end, swapping misplaced odd and even numbers. This partitions the array in O(n) time while using O(1) extra space.
Is Sort Array By Parity asked at Google/Amazon/Meta?
Parity and partition-style array problems frequently appear in interviews at large tech companies such as Amazon, Google, and Meta. While this exact question may vary, the underlying two-pointer partition pattern is commonly tested.
What data structure is used in Sort Array By Parity?
The problem primarily uses arrays and pointer manipulation. The optimal solution relies on the two-pointer technique to partition elements in place without additional data structures.
What is the time complexity of Sort Array By Parity?
The optimal solution runs in O(n) time because each element is examined at most once during the partition process. The in-place two-pointer approach also keeps the space complexity at O(1).