Sponsored
Sponsored
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.
1#include <stdio.h>
2
3void swap(int *a, int *b) {
4 int temp = *a;
5 *a = *b;
6 *b = temp;
7}
8
9void sortArrayByParity(int* nums, int numsSize) {
10 int i = 0, j = numsSize - 1;
11 while (i < j) {
12 if (nums[i] % 2 > nums[j] % 2) {
13 swap(&nums[i], &nums[j]);
14 }
15 if (nums[i] % 2 == 0) i++;
16 if (nums[j] % 2 == 1) j--;
17 }
18}
19
20int main() {
21 int nums[] = {3, 1, 2, 4};
22 int size = sizeof(nums) / sizeof(nums[0]);
23 sortArrayByParity(nums, size);
24 for (int i = 0; i < size; i++) {
25 printf("%d ", nums[i]);
26 }
27 return 0;
28}This C implementation uses two indexes to rearrange the list in place by swapping elements when needed.
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)
1import
In Java, the solution leverages arrays to separately capture even and odd numbers and merge them subsequently.