Move All Odd Numbers to the End of an Array

Title: Move All Odd Numbers to the End of an Array

In this guide, you will learn how to rearrange an integer array so that every even number sits in the front portion and every odd number is pushed to the end. This is a classic partition problem that interviewers use to probe your comfort with the two-pointer technique and in-place array mutation.

We will build a complete Java program, walk through the two-pointer algorithm line by line, trace it on a fresh input, cover the common mistakes that trip learners up, and finish with interview-style follow-ups so you can turn this exercise into real preparation.

Understanding the Problem

You are given an integer array arr. You must rearrange its elements so that all even numbers appear before all odd numbers. The rearrangement should happen in place, which means you may use only a constant amount of extra memory, and the operation should run in a single pass through the array.

There is one subtle detail. The two-pointer approach shown below does not preserve the original relative order of the evens or the odds. If stability matters, you would need an auxiliary array and an O(n) space budget. For most interview variations the in-place, order-not-preserved version is what is being asked.

Approach / Algorithm Steps

We use two pointers that walk toward each other. The left pointer looks for odd numbers that are in the wrong place; the right pointer looks for even numbers that are in the wrong place. When both pointers find a mismatch, we swap and advance.

1. Initialize left to 0 and right to arr.length - 1.
2. While left < right, inspect arr[left] and arr[right].
3. If arr[left] is even, it is already on the correct side, so increment left.
4. Otherwise, if arr[right] is odd, it is already on the correct side, so decrement right.
5. Otherwise arr[left] is odd and arr[right] is even; swap them, then move both pointers inward.
6. The loop ends when the two pointers meet, at which point every even number is on the left and every odd number is on the right.

Java Program

The following program defines a reusable moveOddToEnd method and drives it from main with a sample array so you can run and verify the output immediately.

public class MoveOddToEnd {

    public static void moveOddToEnd(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            if (arr[left] % 2 == 0) {
                left++;
            } else if (arr[right] % 2 != 0) {
                right--;
            } else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {12, 17, 70, 15, 22, 65, 21, 90};
        System.out.print("Original array: ");
        printArray(arr);
        moveOddToEnd(arr);
        System.out.print("Rearranged array: ");
        printArray(arr);
    }
}

Explanation of the Program

The moveOddToEnd method accepts the array and sets up two pointers. left starts at the first index and right starts at the last index. The while loop runs as long as the pointers have not crossed.

Inside the loop, the first branch checks whether arr[left] % 2 == 0. If it is, the element is even and already positioned correctly, so we advance left without touching the array. The second branch handles the mirror case: when arr[right] is odd, it belongs on the right side, so we decrement right.

Only when both pointers point at misplaced elements do we actually swap. The temporary variable temp holds arr[left] while the two cells are exchanged. Both pointers then step toward the middle because the newly swapped values are now in their final homes.

The printArray helper walks the array once and prints each value separated by a space. The main method prints the original and the rearranged arrays so you can compare them side by side.

Step-by-Step Trace

Let us trace the algorithm on the input [8, 1, 7, 2, 10, 5]. The table below shows one row per iteration of the while loop so you can watch each pointer move and each swap take effect.

At the end of each iteration, every element strictly before left is even and every element strictly after right is odd. That is the loop invariant that makes the algorithm correct.

Examples

The following examples show how the method behaves on inputs with different distributions of odd and even values.

Example 1: Mixed array

An input of mixed odds and evens is the typical case. All three branches of the loop fire at least once.

int[] arr = {3, 8, 5, 2, 7, 4};
moveOddToEnd(arr);
printArray(arr);
// Output: 4 8 2 5 7 3

Example 2: Already partitioned

When the evens are already at the front and the odds already at the back, the algorithm performs no swaps. It only advances pointers and finishes in a single pass.

int[] arr = {2, 4, 6, 1, 3};
moveOddToEnd(arr);
printArray(arr);
// Output: 2 4 6 1 3

Example 3: All odd elements

If every element is odd, left never advances and right walks all the way inward until the pointers meet. The output equals the input.

int[] arr = {1, 3, 5, 7};
moveOddToEnd(arr);
printArray(arr);
// Output: 1 3 5 7

Common Mistakes to Avoid

The algorithm looks small, but there are a handful of mistakes that learners make again and again on this problem. Watch out for the following.

• Advancing both pointers on every iteration – calling left++ and right-- unconditionally skips elements the pointers never inspected. Only advance the pointer whose side has been resolved.
• Using <= in the loop condition – writing while (left <= right) lets the pointers compare an element to itself and may swap it with itself. Use left < right so the loop stops exactly when the pointers meet.
• Testing oddness with arr[i] % 2 == 1 – this is false for negative odd numbers in Java because the remainder keeps the sign. Prefer arr[i] % 2 != 0 or (arr[i] & 1) == 1.
• Forgetting the temporary variable – writing arr[left] = arr[right]; arr[right] = arr[left]; clobbers the left value before it can be stored. Use a temp variable or Java’s three-step swap.
• Assuming the relative order is preserved – the two-pointer swap scrambles the order of evens and odds. If a follow-up question demands stability, you need a different algorithm, not a fix to this one.

Edge Cases to Test

A good interview answer walks through the following boundary inputs without being asked. Mention the first three before you start coding.

• Empty array
• Single-element array
• All elements even
• All elements odd
• Already partitioned (evens then odds)
• Reverse partitioned (odds then evens)
• Negative odd numbers such as -3 and -7
• Null array reference

Additional Considerations

The time complexity is O(n), where n is the length of the array. Each pointer moves at most n times and together they visit every index exactly once. The space complexity is O(1) because the only extra storage is the temp variable used during the swap.

Negative numbers deserve a note. In Java, the % operator preserves the sign of the dividend, so -3 % 2 is -1, not 1. Testing value % 2 != 0 handles both positive and negative odd values; testing value % 2 == 1 would miss every negative odd integer.

If the problem required preserving the original relative order of the evens and the odds, the two-pointer swap would not suffice. You would allocate an auxiliary array, copy evens in a first pass and odds in a second, then write the result back. That version runs in O(n) time but uses O(n) extra memory.

Interview Follow-up Questions

Once you solve the base problem, a strong interviewer will probe your understanding with variations. Here are the ones that come up most often, ordered from easiest to hardest.

• Can you preserve the relative order of the evens and odds? – allocate an auxiliary array, write evens in a first pass and odds in a second, then copy back for O(n) time and O(n) extra space.
• Can you partition by any predicate, not just parity? – replace the modulo check with a generic Predicate<Integer> or IntPredicate; the two-pointer skeleton is identical.
• What if the input is an immutable stream rather than an array? – you cannot swap in place; buffer the evens and odds into two queues as the stream arrives, then concatenate them when the stream ends.
• How would you partition the array into three groups: negatives, zeros, and positives? – use the Dutch National Flag three-pointer scheme, which still runs in O(n) time and O(1) space.
• What if the array is so large it does not fit in memory? – partition each chunk on disk, write evens and odds to two output files, then concatenate the files. The chunk step is embarrassingly parallel.

Conclusion

Moving odd numbers to the end of an array is a compact exercise that rewards a clear two-pointer mental model. Once you can state the loop invariant out loud, the implementation almost writes itself, and the common mistakes become easy to spot in your own code.

Try adapting the method to partition by a different predicate, or extend it to the three-way Dutch National Flag problem; both are frequent interview sequels. You can learn more about array techniques here: Arrays.