Remove all occurrences of an element from an array, in place

Question

I solved this problem:

Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn't matter what you leave beyond the new length.

How can I improve its execution time and also, if there is any better way of doing it?

public int removeElement(int[] numbers, int value) {
 int index = 0;
 for(; index < numbers.length; index++) {
 if(numbers[index] == value) {
 boolean otherNumberPresent = false;
 int j = index + 1;
 for(; j < numbers.length; j++ ){
 if(numbers[j] != value) {
 otherNumberPresent = true;
 break;
 }
 }
 if(otherNumberPresent) {
 int temp = numbers[j];
 numbers[j] = numbers[index];
 numbers[index] = temp;
 } else {
 return index;
 }
 }
 }
 return index;
}

Answer 1

A much simpler solution is to have an "input pointer" i and an "output pointer" o.

public int removeElement(int[] numbers, int value) {
 int o = 0;
 for (int i = 0; i < numbers.length; i++) {
 if (numbers[i] != value) {
 numbers[o++] = numbers[i];
 }
 }
 return o;
}

Answer 2

The fundamental issue with your code is that it has two loops in it. As a rule of thumb, that suggests it is a quadratic algorithm: if you double the size of the input, the runtime could be four times worse.

In practice that should (depending on the input profile) happen rarely, so long as the array doesn't have the first half full of the target number and the second full of other stuff. But even with a more random distribution, this will be slower than needed because it keeps dumping the values to remove back into the bit of the array it is about to search!

The answer by 200_success works well enough, but also has a higher than necessary cost because it writes something in almost every step of the loop.

There is another solution, hinted at in the question with the order doesn't matter clause: when you need to delete something, move the replacement from the end. Because the end is discarded anyway, you don't even need to swap out the old value with the one you want to delete.

Although it is dangerous to predict without profiling, that will probably prove a more efficient approach. The heuristic is that most steps in the loop will just be a read and equality comparison before moving on to the next step. (This should also be friendly to a bunch of low level details such as the cache coherence and branch predictor, but that is very detailed and really needs profiling.)