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] <= 5000In #905 Sort Array By Parity, the goal is to rearrange the array so that all even integers appear before the odd integers. The relative order does not matter, which allows for several efficient strategies.
A common and efficient method uses the two pointers technique. One pointer starts at the beginning and another at the end of the array. By checking the parity of the numbers, you can move pointers or swap elements so that even values migrate toward the front while odd values move toward the back. This approach processes the array in a single pass.
Another straightforward approach is to sort or rebuild the array by collecting even numbers first and then appending odd numbers. While simpler to reason about, it may require additional space depending on implementation.
The two-pointer solution typically runs in O(n) time with O(1) extra space, making it the preferred approach for interview scenarios.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers | O(n) | O(1) |
| Extra Array / Rebuilding | O(n) | O(n) |
| Sorting Based Method | O(n log n) | O(1) or O(n) |
Nick White
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.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since no additional data structures are used.
1using System;
2
3class SortArrayByParity {
4 public static void SortArrayByParityMethod(int[] nums) {
5 int i = 0, j = nums.Length - 1;
6 while (i < j) {
7 if (nums[i] % 2 > nums[j] % 2) {
8 int temp = nums[i];
9 nums[i] = nums[j];
10 nums[j] = temp;
11 }
12 if (nums[i] % 2 == 0) i++;
13 if (nums[j] % 2 == 1) j--;
14 }
}
static void Main() {
int[] nums = {3, 1, 2, 4};
SortArrayByParityMethod(nums);
Console.WriteLine(string.Join(", ", nums));
}
}This C# solution uses two pointers to swap odd and even numbers in an array in-place, keeping the even numbers at the front of the array.
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.
Time Complexity: O(n)
Space Complexity: O(n)
1using 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));
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of parity-based array rearrangement is common in coding interviews. It helps assess understanding of arrays, in-place operations, and the two-pointer technique.
The problem primarily relies on array manipulation. Using two pointers within the same array is usually the best option because it avoids additional memory and keeps the time complexity linear.
The optimal approach uses the two-pointer technique. One pointer scans from the beginning and another from the end, swapping elements when an odd number appears before an even number. This method completes in a single pass with constant extra space.
Yes, it can be solved in-place using the two-pointer approach. By swapping elements directly inside the array, you can move even numbers to the front and odd numbers to the back without allocating additional storage.
The C# solution separates the array into even and odd numbers before combining them into one output array.