Java Programmer Java Programmer - 26 days ago 5
Java Question

Removal of negative numbers from an array in java

My Objective is remove all negative numbers from an arrays in Java.

I have write below code, Help me improve the complexity of code or suggest me good algorithm.

public static void main(String[] args) {
int[] array = { 1, -3, 4, -9, 3, 4, 70, -10, 0, 7 };
System.out.println(Arrays.toString(removeNegativeNumbers(array)));
}

public static int[] removeNegativeNumbers(int[] num) {
List<Integer> list = new ArrayList<>();
for (int n : num) {
if (n >= 0) {
list.add(n);
}
}
int[] result = new int[list.size()];
for (int i = 0; i < result.length; i++) {
result[i] = list.get(i).intValue();
}
return result;
}

Answer

This is an in-place O(n) algorithm with constant space (neglecting the space we need for output array). When an element is non-negative, copy the element and advance both output array and input array seeker. And when the element is negative, advance only the input array seeker(indx) and avoid copying to output array.

public static void main(String[] args) {
    int[] array = { 1, -3, 4, -9, 3, 4, 70, -10, 0, 7 };
    System.out.println(Arrays.toString(removeNegativeNumbers(array)));
}

public static int[] removeNegativeNumbers(int[] num) {
    int[] output = new int[num.length];
    int k = 0;
    int i = 0;
    while(i < num.length) {
       if(num[i] >= 0) {
           output[k++] = num[i++];
       } else {
           ++i;
       }
    }
    return Arrays.copyOfRange(output, 0, k);
}

Moreover, You can also transform the input array to hold output like insertion sort way to avoid the space overhead of output array.

public static int[] removeNegativeNumbers(int[] num) {
    int k = 0;
    int i = 0;
    while(i < num.length) {
       if(num[i] >= 0) {
           num[k++] = num[i++];
       } else {
           ++i;
       }
    }
    return Arrays.copyOfRange(num, 0, k);
}
Comments