What is the most efficient method to remove null values within an array.

Question

I am curious what the most efficient method of removing null values in arrays is. Here is my current null(0) removal method.

public static int[] removeNull(int[] array){
        int j = 0;
        for( int i=0;  i<array.length;  i++ )
        {
            if (array[i] != 0)
                array[j++] = array[i];
        }
        int [] newArray = new int[j];
        System.arraycopy( array, 0, newArray, 0, j );
        return newArray;
}

What is this method performance? I was expecting it to be n.

Answer 1

Yes, your method's time complexity is O(n) - your loop has n (the length of the array) iterations, and copying an array requires time proportional to the size of the copied array, which in this case is O(n) in the worst case.

And you can't do better than that (in terms of time complexity), since you have to iterate over the entire array in order to locate the elements that should be removed.

If your goal is to reduce code complexity (i.e. write the shortest amount of code), you can use an IntStream (requires Java 8 or later):

public static int[] removeNull(int[] array) {
    return Arrays.stream(array).filter(i -> i != 0).toArray();
}

As Andreas commented, this solution has the advantage of leaving the original array unchanged.