Efficient way to get indexes of matched items using Lists

Question

I've two lists A and B. I'd like to find out indexes of elements in A that match elements of listB. Something like this:

ArrayList listA = new ArrayList();
listA.add(1);listA.add(2);listA.add(3);listA.add(4);
ArrayList listB = new ArrayList();
listB.add(2);listB.add(4);
ArrayList listC = new ArrayList();
for(int i=0; i<listB.size();i++) {
   int element = listB.get(i);
   for(int j=0; j<listA.size(); j++) {
      if(listA.get(j) == element) listC.add(j);
   }
}

I guess that's one ugly way to doing it. What is the best way to finding all the indexes of A that match all elements in B? I believe there exists a method called containsAll in collections api - don't think it returns matching indexes.

Is there a reason Set's won't work? http://download.oracle.com/javase/1.4.2/docs/api/java/util/Set.html — madmik3, Aug 18 '11 at 12:40
I need indexes of the elements - using a Set is going to be same as using List? — Jay, Aug 18 '11 at 12:52

score 6 · Accepted Answer · answered Aug 18 '11 at 12:55

6

If you had to use an ArrayList, you could create a HashSet from the ArrayList. This would make the call to contains O(1). It would take O(n) to create the HastSet. If you could start with a HashSet, that would be best.

public static void main(String[] args) 
{
    List listA = new ArrayList();
    listA.add(1);
    listA.add(2);
    listA.add(3);
    listA.add(4);
    List listB = new ArrayList();
    listB.add(2);
    listB.add(4);
    Set hashset = new HashSet(listA);

    for(int i = 0; i < listB.size(); i++) 
    {
        if(hashset.contains(listB.get(i))) 
        {
            listC.add(i);
            System.out.println(i);
        }
    }   
}

answered Aug 18 '11 at 12:55

SwDevMan81

48,814
22
151
184

contains() is not so efficient. – DwB Aug 18 '11 at 13:08
so.. there is no way to this other than a minimum complexity of O(n)? – Jay Aug 18 '11 at 13:11
1

looping through n elements in list A and looping through m elements in list B for each element in list A seems to be less efficient than O(n) to me. – DwB Aug 18 '11 at 13:20
looping through n elements in list A happens when you create a HashSet? – Jay Aug 18 '11 at 13:24
@DwB - contains for a HashSet is efficient, its O(1) – SwDevMan81 Aug 18 '11 at 13:27
@Jay - You need to loop to create the HashSet and to Search through one of the ArrayLists. You will only need to loop once if you start with the HashSet and not an ArrayList. – SwDevMan81 Aug 18 '11 at 13:28
Are you sure that the complexity of creating a HashSet from an arraylist is O(n)? – Jay Aug 18 '11 at 13:34
@Jay - Yup (http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf). Add for a HashSet is O(1), but you do it n times. – SwDevMan81 Aug 18 '11 at 13:40
if you do it n times at 0(1) - that is same as O(n), isn't it? So the total complexity would be O(n) + O(n)? Pardon my ignorance - I'm not good with algo complexity. – Jay Aug 18 '11 at 13:45
@Jay - That is correct. If you start out with a HashSet, then you can reduce it to just O(n). But using the way I did with copying the ArrayList to a HashSet and then searching is O(n) + O(n) as you mentioned. – SwDevMan81 Aug 18 '11 at 13:52
btw, this question here http://stackoverflow.com/questions/6986757/efficient-way-to-do-contains-between-two-lists says the complexity would be O(n^2) and not O(n)+O(n) – Jay Aug 18 '11 at 14:02
@Jay - If you look at Jon Skeets comments in his answer, he says the same thing I did. It's O(n) because the lookup in a HashSet is O(1). This answer says the same thing mine does. Turn one of the ArrayLists into a HashSet. – SwDevMan81 Aug 18 '11 at 14:05
O(n^2) assumes table scan of list a and table scan list b for each element in list a. This was my assumption, and (as indicated in comments above) is wrong. – DwB Aug 18 '11 at 14:11

score 2 · Answer 2 · answered Aug 18 '11 at 12:39

2

The Guava libraries come with a method

"SetView com.google.common.collect.Sets.intersection(Set a, Set b)

that will give the elements contained in both sets, but not the indexes. Although it should be easy to get the indexes afterwards.

answered Aug 18 '11 at 12:39

Nodebody

1,433
11
14

2

third party libraries for a simple thing as this? – Jay Aug 18 '11 at 12:52
@Jay, yes, that's Java... I can imagine writing a very straightforward line of LINQ if I were in C# world for a change... – Peter Perháč Aug 18 '11 at 12:59

Maurício Linhares · Answer 3 · 2011-08-18T13:01:18.107

1

Simple:

List<Integer> listA = new ArrayList<Integer>();
listA.add(1);
listA.add(2);
listA.add(3);
listA.add(4);

List<Integer> listB = new ArrayList<Integer>();
listB.add(2);
listB.add(4);

List<Integer> listC = new ArrayList<Integer>();

for ( Integer item : listA ) {
    int index = listB.indexOf( item );
    if ( index >= 0 ) {
        listC.add(index);
    }
}

But this only works if there is no repetition, if there are repeated indexes you have to do it the way you did, navigating the full list.

EDIT

I thought you wanted the elements, not indexes, sets are not going to give you indexes, only the elements.

edited Aug 18 '11 at 13:01

answered Aug 18 '11 at 12:38

Maurício Linhares

39,901
14
121
158

what is the time complexity of using contains() method here? Secondly, I need the indexes not the actual elements at these indexes. – Jay Aug 18 '11 at 12:49
**contains** is an O(n) operation. – Maurício Linhares Aug 18 '11 at 12:52
that's linear complexity. What about finding indexes? – Jay Aug 18 '11 at 12:56
Updated answer and your question title to say **indexes** instead of matching items. – Maurício Linhares Aug 18 '11 at 13:02

mre · Answer 4 · 2011-08-18T13:06:57.103

Assuming there's no duplicate values, why not use ArrayList.indexOf?

public final class ArrayListDemo {
    public static void main(String[]args){
        findIndices(createListA(), createListB());      
    }

    private static final List<Integer> createListA(){
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(3);
        list.add(5);

        return list;
    }

    private static final List<Integer> createListB(){
        List<Integer> list = new ArrayList<Integer>();
        list.add(0);
        list.add(2);
        list.add(3);
        list.add(4);

        return list;
    }

    private static void findIndices(List<Integer> listA, List<Integer> listB){
        for(int i = 0; i < listA.size(); i++){  
            // Get index of object in list b
            int index = listB.indexOf(listA.get(i));

            // Check for match
            if(index != -1){
                System.out.println("Found match:");
                System.out.println("List A index = " + i);
                System.out.println("List B index = " + index);
            }
        }
    }
}

Output

Found match:
List A index = 1
List B index = 2

the `get` runs in constant time (i.e. O(1)) and `indexOf` runs in linear time (i.e. O(n)). — mre, Aug 18 '11 at 13:12
the for loop means - you'll be doing indexOf as many times as the number of elements in A - Do you think SwDevMan81's answer below is more efficient? — Jay, Aug 18 '11 at 13:19

score 1 · Answer 5 · answered Aug 18 '11 at 13:18

If list A and list B are sorted in the same order (I'll assume ascending, but descending works as well) this problem has an O(n) solution. Below is some (informal, and untested) code. When the loop exits, indexMap should contain the indices of every element in list A that match an element in list B and the index of the matched element in list B.

  int currentA;
  int currentB;
  int listAIndex = 0;
  int listBIndex = 0;
  Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();

  currentA = listA.get(listAIndex);
  currentB = listB.get(listBIndex);
  while ((listAIndex < listA.length) && (listBIndex < listB.length))
  {
    if (currentA == currentB)
    {
      indexMap.put(listAIndex, listBIndex);
      ++listAIndex;
    }
    else if (currentA < currentB)
    {
      ++listAIndex;
    }
    else // if (currentA > currentB)
    {
      ++listBIndex;
    }
  }

if the lists are not sorted, I guess - the additional complexity involved in sorting would add up to the total complexity, wouldn't it? — Jay, Aug 18 '11 at 13:22
The complexity becomes the least efficient of the sort vs O(n). Usually that will mean the the complexity of the sort. — DwB, Aug 18 '11 at 13:37

score 0 · Answer 6 · answered Aug 18 '11 at 12:41

0

Using Apache CollectionUtils, there are plenty of options

answered Aug 18 '11 at 12:41

Mike G

4,713
2
28
31

Efficient way to get indexes of matched items using Lists

6 Answers6