CODEWITHSUNDEEP
javaalgorithm
user7117165
user7117165

Reputation:

Removal of negative numbers from an array in Java

My objective is to remove all negative numbers from an array in Java.

I have written the below code. How do I improve the complexity of code or is there a 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;
}

Upvotes: 21

Views: 34588

Answers (8)

MounyaSri
MounyaSri

Reputation: 11

Use iterator

  Iterator<Integer> itr = objArray.iterator();
     while(itr.hasNext()) {
     Integer next = itr.next();
     if(next < 0) {
        itr.remove();
     }
  }

Upvotes: 1

Lova Chittumuri
Lova Chittumuri

Reputation: 3303

Follow the below code (Java 8)

int test[] = new int[] { 15, -40, -35, 45, -15 };
    // here we can take the test array in to stream and filter with condition (>=0).
    int[] positives = Arrays.stream(test).filter(x -> x >= 0).toArray();

    System.out.println("Here is the positive array elements");

    for (int i : positives) {
        System.out.print(i + "\t");
    }

Upvotes: 2

Kaidul
Kaidul

Reputation: 15875

How do I improve the complexity of code or is there a good algorithm?

Here is a linear 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 int[] removeNegativeNumbers(int[] num) {
    int[] output = new int[num.length];
    int k = 0;
    for(int i = 0; i < num.length; i++) {
       if(num[i] >= 0) {
           output[k++] = num[i];
       }
    }
    return Arrays.copyOfRange(output, 0, k);
}

Space Efficient Solution

You can make the algorithm in-place by transforming 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;
    for(int i = 0; i < num.length; i++) {
       if(num[i] >= 0) {
           num[k++] = num[i];
       }
    }
    // Now input array is holding the output data
    // Return the length of output array
    return k;
}

// Usage: int newLen = removeNegativeNumbers(array);

This is called two pointers technique, very simple yet useful to solve many classical puzzles like Array de-duplication, merging two sorted arrays, intersection of two sorted arrays etc.

Upvotes: 24

Insac
Insac

Reputation: 810

I don't think we can get better in terms of efficiency than @kaidul-islam answer (and @user6904265 in terms of conciseness).

I'm just adding a solution that should have some value in a very specific scenario, where negatives rarely appear and array is very large.

Basic idea is to defer the actual copy until a negative value is found and then copy with System.arraycopy. In case no negative is found, the source array would be returned. 

import java.util.*;

public class NotNegativeTest {

    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; 
         int last=-1;
         int howmany=0;

         while(i < num.length) {
             if(num[i] < 0) {
                howmany=i-last-1;
                switch(howmany) {
                    case 0: break;
                    case 1: 
                            output[k]=num[last+1];
                            k++;
                            break;
                    default:        
                            System.arraycopy(num, last+1,  output, k, howmany);
                            k+=howmany;
                }
                last=i;
             } 
             i++;
         } 
         if (last>=0) {
              if(last!=i-1) {
                howmany=i-last-1;  
                System.arraycopy(num, last+1,  output, k, howmany);
                k+=howmany;
            }
        } else {
            return num;
        }

         return Arrays.copyOfRange(output, 0, k);
     }

}

I've found the time to write a JMH microbenchmark.

I've used used these configurations:

Options opts = new OptionsBuilder()
  .include(MyBenchmark.class.getSimpleName())
  .mode(Mode.AverageTime)
  .warmupIterations(1)
  .warmupTime(TimeValue.seconds(5))
  .measurementIterations(10)
  .measurementTime(TimeValue.seconds(5))
  .jvmArgs("-server")
  .forks(1)
  .build();
new Runner(opts).run();

(disclaimer: my first JMH test, so if someone has some suggestions, I'll be glad to change it and update the results)

And here are the results:

# Run complete. Total time: 00:02:54

Benchmark                             Mode  Cnt  Score   Error  Units
MyBenchmark.testMethodUser6904265     avgt   10  0,201 ± 0,040   s/op
MyBenchmark.testMethodInsac           avgt   10  0,093 ± 0,022   s/op
MyBenchmark.testMethodKaidul          avgt   10  0,124 ± 0,029   s/op

Now, before cheering me, please take a look to how biased the test was:

 int[] array = new int[10000000];
 array[0]=-5;
 array[10000]=-3;
 array[40000]=-3;
 array[8000000]=-3;

 int[] answer=NotNegativeTest.removeNegativeNumbers(array);

So here the thing to notice it is not that my method won (the test was written for my method to win :-) but how close the generic kaidul-islam method was to mine even in this extreme scenario.

UPDATED: here is the link to the jmh benchmark I wrote so you can verify more realistic scenario (if someone finds issues with how I setup the test, please let me know). There is a depenendency on Trove for a test I've done on another answer.

Upvotes: 9

Ryan Amos
Ryan Amos

Reputation: 5452

Since you will necessarily need to look at each individual element to determine if it is less than 0, the runtime must be at least O(n). Since the space needed to store the input is O(n), the space is at least O(n). Your solution runs in O(n) time with O(n) complexity, therefore no solution can have better space or runtime complexity than your solution

We can, however, get better results if we assume the array is sorted. Then, we do a binary search for 0. If we have a way to return the sub-array with constant time (e.g. pointer magic in C, or by simply returning the start index to be read), then the algorithm would have O(log n) time.

Upvotes: 1

user6904265
user6904265

Reputation: 1938

What about Java 8 streams?

Arrays.stream(num).filter(s -> s >= 0).toArray();

Upvotes: 53

Mangu Singh Rajpurohit
Mangu Singh Rajpurohit

Reputation: 11420

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

Upvotes: 0

Naomi
Naomi

Reputation: 5486

This will do it in-place with a single iteration:

Hold 2 indexes: src and dst on the original array. both are initialized to 0.

when a number is positive, copy it from num[src] to num[dst] and advance both indexes

when a number is negative, just advance src.

return the original array with dst as its new size.

public static int removeNegativeNumbers(int[] num) {
  int dst=0;
  for (int src=0 ; src<num.length ; ++src)
    if (num[src]>=0)
      num[dst++] = num[src];
  return dst;
}

Upvotes: 7

Related Questions