3

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.

joshLor
  • 1,034
  • 1
  • 12
  • 27

2 Answers2

5

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.

Eran
  • 387,369
  • 54
  • 702
  • 768
  • 1
    Entirely agree. +1 However, code complexity can be improved by replacing last 3 lines with [`return Arrays.copyOf(array, j);`](https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#copyOf-int:A-int-) – Andreas Dec 21 '17 at 06:40
  • would these mean that the entire array function works in 2n? Or does that not make any sense, sorry I am new to this efficiency stuff. – joshLor Dec 21 '17 at 06:44
  • @Andreas well, if the goal is to reduce the amount of code, you can use an IntStream and solve the problem with a single line of code. – Eran Dec 21 '17 at 06:45
  • 2
    @joshLor yes, though `2n` is asymptotically `O(n)`. – Eran Dec 21 '17 at 06:45
  • so if I am getting this right 2n is the same thing as O(n) and 2n is also the same thing as O(n). – joshLor Dec 21 '17 at 06:48
  • 1
    @Eran True, but I was sticking to plain non-stream Java, since so many on here are still pre-Java 8 Android users. --- One more +1 from me for adding stream solution. *(Wish I could do another +1)* – Andreas Dec 21 '17 at 06:48
  • 2
    @joshLor `2n is the same thing as O(n) and 2n is also the same thing as O(n)` - you got that right, twice :) – Eran Dec 21 '17 at 06:49
  • 1
    *Suggested clarification:* Stream solution is for Java 8+, and has the advantage that it leaves original array unmodified. – Andreas Dec 21 '17 at 06:51
  • 1
    @Eran I like the explanation, I did not even realize from the start that it's still `O(n)` even with copying, but this still traverses it twice. plus one – Eugene Dec 21 '17 at 11:01
0
Use filter method,

import java.util.Arrays;
import java.util.stream.Collectors;

public class RemoveNullValue {
    public static void main( String args[] ) {
        String[] firstArray = {"test1", "", "test2", "test4", "", null};

        firstArray = Arrays.stream(firstArray)
                     .filter(s -> (s != null && s.length() > 0))
                     .toArray(String[]::new);    

    }
}
Shreya Prajapati
  • 114
  • 12
  • 1
    An `int` is not very probable to be `null`. In fact, I don't expect this to compile. – daniu Dec 21 '17 at 06:33
  • can check int with value of 0 and need to use Java 8 – Shreya Prajapati Dec 21 '17 at 06:38
  • 1
    Still won't make code compile, since input is an `int[]`, not an `ArrayList` – Andreas Dec 21 '17 at 06:42
  • can use Arrays.stream(arrayList).filter() for int[] from [link](https://stackoverflow.com/questions/4150233/remove-null-value-from-string-array-in-java) String[] firstArray = {"test1", "", "test2", "test4", "", null}; firstArray = Arrays.stream(firstArray) .filter(s -> (s != null && s.length() > 0)) .toArray(String[]::new); – Shreya Prajapati Dec 21 '17 at 06:44
  • You should edit answer and fix it, rather than having (unformatted) code in a comment. Right now, answer is still wrong. – Andreas Dec 21 '17 at 06:51