39

I have two arrayLists and I am trying to "subtract" one arrayList from another. For example, if I have one arrayList [1,2,3] and I am trying to subtract [0, 2, 4] the resulting arrayList should be [1,3]. 

List<Integer> a = new ArrayList<>(Arrays.asList(1, 2, 3));
List<Integer> b = Arrays.asList(0, 2, 4);
subtract(a,b) // should return [1,3]

Here is my code.

//returns a new IntSet after subtracting a from b
// .minus().toString()
ArrayList<Integer> minusArray = new ArrayList<Integer>();

    minusArray.addAll(array1);

    for(int i =0; i< minusArray.size(); i++){
        for(int j = 0; j < array2.size(); j++){
            if(minusArray.get(i).equals(array2.get(j))){
                minusArray.remove(i);
                if(i == 0){
                    ;
                }
                else if(j == 0){
                    ;
                }
                else{
                    i = 0;
                    j = 0;
                }
            }
            else{}
        }
    }

return minusArray;

My code works in some cases, like if arrayList1 = [4,6] and arrayList2 = [6] it will will give me a result of [4]. But if I try something like [1,2,4] and [0,4,8]

I get this exception:

java.lang.IndexOutOfBoundsException: Index: 2, Size: 2
    at java.util.ArrayList.rangeCheck(Unknown Source)
    at java.util.ArrayList.get(Unknown Source)
    at IntSet.minus(IntSet.java:119)
    at IntSetDriver.main(IntSetDriver.java:62)

Here is the code I have come up with. I have done test runs through it and to me I think it should work. The user inputs these arrayLists and they are presorted, I also do not know Hash or big-O. 

ArrayList<Integer> minusArray = new ArrayList<Integer>();

    minusArray.addAll(array1);

    for(int i =0; i< minusArray.size(); i++){
        for(int j = 0; j < array2.size(); j++){
            if(minusArray.get(i).equals(array2.get(j))){
                minusArray.remove(i);
            }
            else{}
        }
    }

return minusArray;
Improve this question
2
  • Since your code tests equals() on each element in the array and removes if true. You can simply use removeAll() like suggested by this answer: stackoverflow.com/a/23172547/1485527. Or am I missing something? If you want only remove the first occurrence go with Apache Utils or plain java, like suggested here stackoverflow.com/a/49415419/1485527. Otherwise I'd like to suggest to provide your solution in form of an answer, and explain why it is the best. Including the answer into the question breaks Q&A style. Commented Apr 26, 2018 at 8:54
  • Java 8: stackoverflow.com/a/49850546/1216775 Commented Jun 13, 2019 at 4:32

9 Answers 9

Reset to default
65

Is there some reason you can't simply use List.removeAll(List)?

    List<Integer> one = new ArrayList<Integer>();
    one.add(1);
    one.add(2);
    one.add(3);
    List<Integer> two = new ArrayList<Integer>();
    two.add(0);
    two.add(2);
    two.add(4);
    one.removeAll(two);
    System.out.println(one);

    result: "[1, 3]"
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

removeAll(2) will remove all occurrences of 2 which is not how subtracting is defined usually. Usually it is meant to remove only on occurrence of 2. Correct? See stackoverflow.com/a/49415419/1485527
Unspecified by the OP. But, the code posted seems to be attempting to remove all in the inner for{} loop. Looks like that's the intention?
hm, your right. It tests for remove() on all elements. So this should clearly be the accepted answer. I will still leave my answer at this place for further reference.
> this should clearly be the accepted answer Feel free to tell the OP that. ;)
45

Try to use subtract method of org.apache.commons.collections.CollectionUtils class.

Returns a new Collection containing a - b. The cardinality of each element e in the returned Collection will be the cardinality of e in a minus the cardinality of e in b, or zero, whichever is greater.

CollectionUtils.subtract(java.util.Collection a, java.util.Collection b)

From Apache Commons Collections

Improve this answer

2 Comments

@kukis CS 251 will be a second year computer science course at some university.
In java 8 you can do b.forEach((i)->a.remove(i)); See: stackoverflow.com/a/49415419/1485527 for further info.
24

Java 8

You can also use streams:

List<Integer> list1 =  Arrays.asList(1, 2, 3);
List<Integer> list2 =  Arrays.asList(1, 2, 4, 5);
List<Integer> diff = list1.stream()
                          .filter(e -> !list2.contains(e))
                          .collect (Collectors.toList()); // (3)

This answer does not manipulate the original list. If intention is to modify the original list then we can use remove. Also we can use forEach (default method in Iterator) or stream with filter.

Using ListUtils

Another option is to use ListUtils if we are using Apache common:

ListUtils.subtract(list, list2)

This subtracts all elements in the second list from the first list, placing the results in a new list. This differs from List.removeAll(Collection) in that cardinality is respected; if list1 contains two occurrences of null and list2 only contains one occurrence, then the returned list will still contain one occurrence.

Improve this answer

3 Comments

How is this better than list1.removeAll(list2) ? In my opinion ( and others) this is not subtracting, because it removes all occurrences of a value in list2 from list1. Or am I missing something?
@jschnasse it returns the difference between two lists and yes it is subtraction. Here intention is to return result rather than manipulating the original list. If we want to remove from original list then we can use remove.
I feel ...though it works , ....its not a good at all ! thats because: 1) when no of elements is less in each list, u must not use stream 2) .contains( ) is not always the criteria for equality(not OP case) eg. what if remove all strings from list1<String> when any element of list1 is substring of list2<String> 3) sometimes Stream1.operation is dependent on Stream2.criteria, then too many string colludes the memory and degrades latency Happy if sum1 tells I'm wrong and suggests best optimized + efficient solutions
7

Traversing the minusArray using an index is one way to do this, but I suggest you make use of the contains(Object) method, which will allow you then to use remove(Object) for the particular element of array2.

Of course, there's always the removeAll(Collection) which does pretty much everything you need...

Improve this answer

Comments

6

You can use org.apache.commons.collections.ListUtils and make all that you want in only one line =)

List resultList = ListUtils.subtract(list, list2);
Improve this answer

Comments

5

Your problem is that in your minusArray.remove(...) call you may shrink the size of the minusArray. To fix this, start at array.size() - 1 and count backwards to 0

Check that - even that won't fix it. You need to reverse the order of your loops

Improve this answer

Comments

2

I'm guessing you get the range problem because you've eliminated one of the elements which changes what the inner loop is looking for (I know this problem occurs when dealing with normal Lists and Collections).

What I've had to do in the past to work around this, is to create a list of items that need to be removed (that is ones that are found in the original list). Iterate through that new list and directly eliminate the original list's elements without having to have an iterator moving through it.

Improve this answer

Comments

2

Try this answer if removeAll() is not what you want. e.g. if you are interested in something like Calculating difference of two lists with duplicates

subtract(a,b)

b.forEach((i)->a.remove(i));

a now contains

[1, 3]

This follows the suggestion of Guava implementors on how to implement subtract

"create an ArrayList containing a and then call remove on it for each element in b."

Which behaves like this implementation used in Apache commons

Difference to removeAll()

[1,2,2,3].removeAll([1,2,3]) //is empty
[1,2,3].forEach((i)->[1,2,2,3].remove(i)); //a is [2]
Improve this answer

Comments

1

My parameterized solution would be like:

<T> ArrayList<T> subtract(ArrayList<T> alpha, ArrayList<T> beta) {
    ArrayList<T> gamma = new ArrayList<T>();
    alpha.forEach(n -> {if (!beta.contains(n)) gamma.add(n); });
    return gamma;
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.