Remove Even Integers From an Array

Given a list of integers, remove every even number. The odd numbers that remain must keep their original order.

Example 1

Input:  [1, 2, 4, 5, 10, 6, 3]
Output: [1, 5, 3]

Example 2

Input:  [-3, -2, 0, 7]
Output: [-3, 7]
Explanation: 0 and -2 are even. In Java, -3 % 2 == -1, because % keeps the sign of the left operand. Test with `x % 2 != 0` (not `x % 2 == 1`).

Brute force: call remove on each even value

Walk an ArrayList with an index i. When the element at i is even, remove it. remove(i) shifts every later element one place left, so the next element moves into position i, and i must not advance. (ArrayList is Java's growable list. remove(int index) removes by position.)

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void removeEven(List<Integer> nums) {
        int i = 0;
        while (i < nums.size()) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i); // O(n): shifts the later elements left by one
            } else {
                i++;
            }
        }
    }

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(List.of(1, 2, 4, 5, 10, 6, 3));
        List<Integer> b = new ArrayList<>(List.of(-3, -2, 0, 7));
        removeEven(a);
        removeEven(b);
        System.out.println(a + " " + b);
    }
}

[1, 5, 3] [-3, 7]

i is an int, so nums.remove(i) removes by position. Calling remove with an Integer object would remove by value instead.

Time: O(n²). If most values are even, each of up to n removals shifts up to n elements. Space: O(1).

Optimal: read index and write index

Instead of closing each gap as soon as it appears, copy each odd value forward to the next free slot:

• read visits every element.
• write is where the next odd value goes. Everything before write is the finished result.

At the end, the first write elements are the answer. An array cannot shrink, so the method returns write as the new length. For a list, nums.subList(write, nums.size()).clear() cuts off the rest.

Walkthrough with [1, 2, 4, 5, 10, 6, 3]:

The new length is 3, so the result is [1, 5, 3].

import java.util.Arrays;

public class Main {
    static int removeEven(int[] nums) {
        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            if (nums[read] % 2 != 0) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }

    static void show(int[] nums) {
        int k = removeEven(nums);
        System.out.print(Arrays.toString(Arrays.copyOf(nums, k)) + " ");
    }

    public static void main(String[] args) {
        show(new int[]{1, 2, 4, 5, 10, 6, 3});
        show(new int[]{-3, -2, 0, 7});
        show(new int[]{2, 4, 6});
        System.out.println();
    }
}

[1, 5, 3] [-3, 7] []

Time: O(n): each element is read once and written at most once. Space: O(1).

Using the standard library

List.removeIf implements this same single pass for an ArrayList:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(1, 2, 4, 5, 10, 6, 3));
        nums.removeIf(x -> x % 2 == 0);
        System.out.println(nums);

        // If you need a new array and must keep the input unchanged:
        int[] input = {1, 2, 4, 5, 10, 6, 3};
        int[] odds = Arrays.stream(input).filter(x -> x % 2 != 0).toArray();
        System.out.println(Arrays.toString(odds));
    }
}

[1, 5, 3]
[1, 5, 3]

removeIf on an ArrayList is O(n) time and O(1) extra space. The filter + toArray version is O(n) time and O(n) space for the new array. List.of(...) returns an unmodifiable list, so the example copies it into an ArrayList before removing.

Edge cases

• Empty input: returns an empty result.
• All even: returns an empty result. All odd: returns the input unchanged.
• Negative odd numbers: x % 2 is -1 for negative odd x in Java, so check x % 2 != 0. (x & 1) == 1 also works for int, because Java integers use two's complement.