Rearrange Even and Odd Numbers in an Array

Title: Rearrange Even and Odd Numbers in an Array

Rearranging an array so that every even number appears before every odd number is a classic array manipulation problem, and it shows up often in coding interviews. In this guide, we’ll explore how to rearrange even and odd numbers in an array using Java with an efficient, in-place two-pointer approach. We’ll walk through the algorithm, trace it on a sample input, and cover the edge cases and follow-up questions an interviewer is likely to ask.

Understanding the Problem

Given an array of integers, the goal is to rearrange its elements so that all even numbers come before all odd numbers. The relative order of elements does not need to stay the same; what matters is that the final array splits cleanly into an even half followed by an odd half.

For example, an input array like {12, 34, 45, 9, 8, 90, 3} should be rearranged so every even value, such as 12, 34, 90, and 8, appears before every odd value, such as 45, 9, and 3.

Approach to Rearrange Even and Odd Numbers

The most efficient way to solve this in place, without extra arrays, is a two-pointer partition similar to the one used in quicksort. One pointer scans from the left looking for odd values, the other scans from the right looking for even values, and the two swap when they meet a mismatch.

Here are the steps:

1. Initialize two pointers: left at index 0 and right at the last index of the array.
2. Repeat the following checks while left is less than right.
3. If numbers[left] is even, that element is already on the correct side, so increment left and continue.
4. Otherwise, if numbers[right] is odd, that element is already on the correct side, so decrement right and continue.
5. If neither shortcut applies, numbers[left] is odd and numbers[right] is even, so swap the two values.
6. After a swap, move both pointers inward by incrementing left and decrementing right.
7. Stop once left meets or crosses right; at that point every even value sits before every odd value.

Java Program to Rearrange Even and Odd Numbers

Let’s implement the two-pointer approach described above in Java:

import java.util.Arrays;

public class RearrangeEvenOdd {

    public static void rearrange(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            if (numbers[left] % 2 == 0) {
                left++;
            } else if (numbers[right] % 2 != 0) {
                right--;
            } else {
                int temp = numbers[left];
                numbers[left] = numbers[right];
                numbers[right] = temp;
                left++;
                right--;
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {12, 34, 45, 9, 8, 90, 3};
        rearrange(numbers);
        System.out.println("Rearranged array: " + Arrays.toString(numbers));
    }
}

Explanation of the Program

• The method rearrange takes an int[] array and mutates it in place, so it returns nothing; the caller’s array is modified directly.
• Two index variables, left and right, start at opposite ends of the array and move toward each other.
• The first if skips over even values that are already positioned before left.
• The else if skips over odd values that are already positioned after right.
• The final else branch only runs when numbers[left] is odd and numbers[right] is even, so swapping them correctly moves each value to its proper half.
• The loop ends when the pointers meet, which guarantees every index is visited once, giving the method O(n) time complexity.

Step-by-Step Trace

Let’s trace the algorithm on the input {3, 8, 5, 12, 7, 4} and watch how left and right converge until the array settles into [4, 8, 12, 5, 7, 3].

At the end of each iteration, every index before left holds an even number and every index after right holds an odd number.

Examples

Let’s see the rearrange method in action on a few different inputs.

Example 1: Mixed Even and Odd Values

A typical mix of even and odd values, including duplicates in parity, ends up fully partitioned:

int[] numbers = {12, 34, 45, 9, 8, 90, 3};
rearrange(numbers);
System.out.println("Rearranged array: " + Arrays.toString(numbers));
// Output: Rearranged array: [12, 34, 90, 8, 9, 45, 3]

Example 2: Array with Negative Numbers

Negative numbers follow the same even and odd rules as positive ones, so the partition still holds:

int[] numbers = {-3, -8, 7, -2, 5, 10};
rearrange(numbers);
System.out.println("Rearranged array: " + Arrays.toString(numbers));
// Output: Rearranged array: [10, -8, -2, 7, 5, -3]

Example 3: Minimal Two-Element Array

The smallest interesting case is a two-element array where a single swap does all the work:

int[] numbers = {1, 2};
rearrange(numbers);
System.out.println("Rearranged array: " + Arrays.toString(numbers));
// Output: Rearranged array: [2, 1]

Common Mistakes to Avoid

These are the mistakes candidates most often make when implementing this partition by hand.

• Checking odd with % 2 == 1 – fails for negative odd numbers like -5, because -5 % 2 evaluates to -1 in Java, not 1. Use % 2 != 0 instead so both positive and negative odd values are caught.
• Swapping on every comparison – swapping numbers[left] and numbers[right] even when numbers[left] is already even overwrites a value that did not need to move and corrupts the partition. Only swap inside the final else branch, when neither shortcut condition matched.
• Forgetting to move both pointers after a swap – advancing only left or only right after a swap leaves the already-placed value at the other end to be re-examined, which can loop forever or scramble the result. Increment left and decrement right together immediately after every swap.
• Expecting the original relative order to survive – this swap-based partition does not preserve the order evens or odds appeared in, so a test asserting [12, 34, 8, 90, ...] in input order will fail even though the partition is correct. If stable order matters, copy evens and odds into a new array in one pass instead of swapping in place.

Edge Cases to Test

Before calling this solved, test the method against these boundary inputs.

• Empty array
• Single-element array
• All even elements
• All odd elements
• Negative numbers mixed with positives
• Zero present (0 counts as even)
• Integer.MIN_VALUE present

Additional Considerations

The rearrange method runs in O(n) time because left and right together scan each index at most once before they meet. Space complexity is O(1) since the swap happens in place and no auxiliary array is allocated.

The trade-off for this in-place speed is that the original relative order within the even group and within the odd group is not preserved. If a caller needs a stable partition, a simple alternative is to make two passes: copy every even value into a new array in the order encountered, then append every odd value. That approach costs O(n) extra space but keeps each group’s original order intact.

Zero is worth calling out explicitly during testing since 0 % 2 == 0 is true, so it is always treated as even, which matches mathematical convention but can surprise a reader skimming the code quickly.

Interview Follow-up Questions

Once the base solution works, an interviewer will usually push further with questions like these.

• What if the relative order of evens and odds must be preserved? – make two passes and copy values into a new array, evens first then odds, which costs O(n) extra space but keeps each group stable.
• What if the array only contains two distinct values, such as 0s and 1s? – this is the same two-pointer idea applied to a binary partition, often called the Dutch National Flag problem for two colors.
• What if you need to separate three categories instead of two, such as negative, zero, and positive numbers? – extend to a three-way Dutch National Flag partition using low, mid, and high pointers instead of just left and right.
• What if the numbers arrive as a stream of unknown length instead of a fixed array? – in-place swapping no longer works because you cannot look ahead; instead buffer odd values in a queue and emit even values immediately, flushing the queue once the stream ends.

Conclusion

Rearranging even and odd numbers in an array comes down to a single pass with two pointers: one chasing odd values from the left, the other chasing even values from the right, swapping whenever they disagree. The result is an O(n) time, O(1) space solution that touches every element exactly once.

Feel free to adapt the rearrange method for your own projects, and keep the edge cases and follow-up questions above in mind the next time this problem comes up in an interview. Happy coding!

You can learn more about Array manipulation techniques: Arrays and Sorting