Problem

Given an integer array arr containing both even and odd numbers, reorder the array so that all even numbers appear before all odd numbers. The relative order among evens or among odds does not need to be preserved unless otherwise specified.

Examples

Example 1

1
2

Input: arr = [1, 2, 3, 4, 6, 8, 7, 12]
Possible output: [12, 2, 8, 4, 6, 3, 7, 1]

Follow up

What if order among evens and odds need to be preserved.

Similar Problems

Solution

Below are common ways to partition an array by parity.

Method 1 — Two-pointer in-place swap (unordered partition)

Intuition

Use two pointers left and right at the ends of the array. Move left forward until it finds an odd number and move right backward until it finds an even number. Swap those two elements. Repeat until left >= right.

This partitions evens to the left and odds to the right in-place, but it does not preserve the original order (unstable).

Approach

  1. Initialize left = 0, right = len(arr) - 1.
  2. While left < right:
    • While left < right and arr[left] is even, left++.
    • While left < right and arr[right] is odd, right--.
    • If left < right, swap arr[left] and arr[right], then left++, right--.
  3. Return arr (now partitioned).

Edge cases:

  • Empty array -> return empty array.
  • All-even or all-odd arrays -> no swaps performed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
 public:
  std::vector<int> arrange(std::vector<int> arr) {
    int left = 0, right = (int)arr.size() - 1;
    while (left < right) {
      while (left < right && (arr[left] % 2) == 0) ++left;
      while (left < right && (arr[right] % 2) != 0) --right;
      if (left < right) {
        std::swap(arr[left], arr[right]);
        ++left; --right;
      }
    }
    return arr;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

package main

type Solution struct{}

// arrange reorders array with even numbers first (in-place)
func (s Solution) arrange(arr []int) []int {
  left, right := 0, len(arr)-1
  for left < right {
    for left < right && arr[left]%2 == 0 {
      left++
    }
    for left < right && arr[right]%2 != 0 {
      right--
    }
    if left < right {
      arr[left], arr[right] = arr[right], arr[left]
      left++
      right--
    }
  }
  return arr
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
  // non-static instance method `arrange`
  public int[] arrange(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
      while (left < right && arr[left] % 2 == 0) left++;
      while (left < right && arr[right] % 2 != 0) right--;
      if (left < right) {
        int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp;
        left++; right--;
      }
    }
    return arr;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
  def arrange(self, arr: list[int]) -> list[int]:
    left, right = 0, len(arr) - 1
    while left < right:
      while left < right and arr[left] % 2 == 0:
        left += 1
      while left < right and arr[right] % 2 != 0:
        right -= 1
      if left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

Complexity

  • ⏰ Time complexity: O(n) — each element is examined at most once by the two pointers.
  • 🧺 Space complexity: O(1) extra space (in-place).

Method 2 — Stable partition using an auxiliary array

Intuition

If the relative order of evens/odds must be preserved, collect evens into one list and odds into another, then concatenate evens followed by odds.

Approach

  1. Create two lists evens and odds.
  2. Iterate arr and append each even element to evens and each odd to odds.
  3. Return evens + odds.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
 public:
  // stable arrange: returns a new vector with evens followed by odds (order preserved)
  std::vector<int> arrange(std::vector<int> arr) {
    std::vector<int> evens; evens.reserve(arr.size());
    std::vector<int> odds; odds.reserve(arr.size());
    for (int x : arr) {
      if (x % 2 == 0) evens.push_back(x);
      else odds.push_back(x);
    }
    evens.insert(evens.end(), odds.begin(), odds.end());
    return evens;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

package main

type Solution struct{}

// stable arrange: returns a new slice with evens first (order preserved)
func (s Solution) arrange(arr []int) []int {
  evens := make([]int, 0, len(arr))
  odds := make([]int, 0, len(arr))
  for _, v := range arr {
    if v%2 == 0 { evens = append(evens, v) } else { odds = append(odds, v) }
  }
  return append(evens, odds...)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import java.util.*;

class Solution {
  // stable arrange: returns a new array with evens followed by odds (order preserved)
  public int[] arrange(int[] arr) {
    List<Integer> evens = new ArrayList<>();
    List<Integer> odds = new ArrayList<>();
    for (int x : arr) {
      if (x % 2 == 0) evens.add(x); else odds.add(x);
    }
    int[] res = new int[arr.length];
    int i = 0;
    for (int v : evens) res[i++] = v;
    for (int v : odds) res[i++] = v;
    return res;
  }
}
1
2
3
4
5
6

class Solution:
    # stable arrange: preserves relative order within evens and odds
    def arrange(self, arr: list[int]) -> list[int]:
        evens = [x for x in arr if x % 2 == 0]
        odds = [x for x in arr if x % 2 != 0]
        return evens + odds

Complexity

  • ⏰ Time complexity: O(n) — single pass to split and linear concatenation.
  • 🧺 Space complexity: O(n) extra space to hold evens and odds.

Method 3 — Use language/library partition helpers

Intuition

Many standard libraries provide partition functions that move elements satisfying a predicate to the front. For example, std::partition (C++) or filter-based constructs can express the same idea concisely.

Code (brief examples)

C++
1
2
3
4
5
6
7
8
9

// Use std::partition to move evens before odds (in-place). This is linear time.
#include <algorithm>
class Solution {
 public:
  std::vector<int> arrange(std::vector<int> arr) {
    std::partition(arr.begin(), arr.end(), [](int x){ return x % 2 == 0; });
    return arr;
  }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

package main

import "sort"

type Solution struct{}

// arrange uses sort.SliceStable helper to group evens first while preserving order
func (s Solution) arrange(arr []int) []int {
  sort.SliceStable(arr, func(i, j int) bool { return (arr[i] % 2) < (arr[j] % 2) })
  return arr
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
import java.util.stream.*;

class Solution {
  // arrange using streams to collect evens then odds (concise library usage)
  public int[] arrange(int[] arr) {
    int[] evens = Arrays.stream(arr).filter(x -> x % 2 == 0).toArray();
    int[] odds = Arrays.stream(arr).filter(x -> x % 2 != 0).toArray();
    int[] res = new int[arr.length];
    System.arraycopy(evens, 0, res, 0, evens.length);
    System.arraycopy(odds, 0, res, evens.length, odds.length);
    return res;
  }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# list comprehensions
class Solution:
    # library helper: sorted with key partitions by parity (stable), or use comprehensions
    def arrange(self, arr: list[int]) -> list[int]:
        # Option A: stable partition via sorted (O(n log n))
        return sorted(arr, key=lambda x: x % 2)

        # Option B: list comprehensions (O(n)) — shown elsewhere in Method 2
        # evens = [x for x in arr if x % 2 == 0]
        # odds = [x for x in arr if x % 2 != 0]
        # return evens + odds

Complexity

  • ⏰ Time complexity: O(n).
  • 🧺 Space complexity: depends on API: O(1) for in-place partition helpers, O(n) for filters/concatenation.