Nested loop complexity

Question

I have several lists of varying size, each index of the list contains both a key and an object : list1.add('Key', obj).

The lists are all sorted.

My aim is to iterate through the list and match 1 or more items in list 2,3,4 or n to an item in the mainList using the key.

Currently I do something along the lines of:

for i to list1 size
   for j to list2 size
   if list1[i] = list2[j]
      do stuff 

As I loop through I'm, using boolean values to exit quickly using a if current != previous check and I'm deleting the object from the list I take it from.

it's working fine but I now have another list that I need to match and possible another n lists afterwards. The lists are of different sizes.

the 2 options that I can see are to either repeat the above segment of code several times where the inner list is changed - I do no like this approach.

The other option is to extend the above and once one inner loop is finished, move onto the next:

  for i to list1 size
       for j to list2 size
       if list1[i] = list2[j]
          do stuff 
       for k to list2 size
       if list1[i] = list2[k]
          do stuff 

I'd like to think I'm correct in thinking that the 2nd is more efficient however I'm unsure. Also, is there a better way?

Thanks for any advice / help.

Answer 1

If the lists are all sorted then you only need to iterate though each list once; on each iteration of the main list, iterate through a secondary list (starting at the previously saved index, initialized to 0) until you find an index whose value is greater than the current value of the main list, save this index, and proceed to the next secondary list.

Array<Integer> indices = new Array(n-1); // indices for every list except list1
for(int i = 0; i < indices.size; i++) {
  indices[i] = 0;
}

for(int i = 0; i < list1.size; i++) {
  Value curVal = list1[i];
  while(indices[0] < list2.size && list2[indices[0]] <= curVal) {
    if(list2[indices[0]] == curVal) {
      // do stuff on list2[indices[0]]
    }
    indices[0]++;
  }
  while(indices[1] < list3.size && list3[indices[1]] < curVal) {
    if(list3[indices[1]] == curVal) {
      // do stuff on list3[indices[1]]
    }
    indices[1]++;
  }
  // etc
}

You can avoid the copy-pasting by using something like a ListIterator that contains a list and its current index; then on each iteration of the main loop you'll iterate through a list of ListIterators in lieu of the copy-pasted code block

public class ListIterator {
  int index = 0;
  List<Value> list;
  Value curVal() {
    return list[index];
  }
  boolean hasNext() {
    return (index < list.size);
  }
}

List<ListIterator> iterators;
for(int i = 0; i < list1.size; i++) {
  Value curVal = list1[i];
  for(int j = 0; j < iterators.size; j++) {
    ListIterator iterator = iterators[j];
    while(iterator.hasNext() && iterator.curVal() <= curVal) {
      if(iterator.curVal() == curVal) {
        // do something with iterator.curVal()
      }
      iterator.index++;
    }
  }
}

This is time complexity O(n) where n is the sum of the lengths of all of your lists

---

Edit: If it's difficult to compare keys via <=, then you can use a Set implementation instead. Add the List1 keys to a Set, then iterate through the remaining lists testing for set membership.

Set<String> set = new Set(List1);
Array<List> lists = new Array();
// add lists to Array<List>

for(int i = 0; i < lists.size; i++) {
  List currentList = lists[i];
  for(int j = 0; j < currentList.size; j++) {
    if(set.contains(currentList[j]) {
      // do something
    }
  }
}