CODEWITHSUNDEEP
javaperformancearraylistdata-structures
Farooq Khan
Farooq Khan

Reputation: 305

How to check for missing elements in two array lists of different objects, in Java?

I have two classes with different properties and only one with a common one. I want to compare the two and extract a list with missing elements. So for example we have the following classes where inventoryId and id are the same and these are elements we'll be looking for, if they're missing in drug list.

public class DrugInventory {
    String inventoryId;
    String drugStatus;
}

public class Drug{
    String id;
    String name;
    String quantity;
}

inventoryID in DrugInventory is equal to id in Drug. So these are two values I'll be looking if they're missing in the Drug list.

List<DrugInventory> drugInventories = new ArrayList<>();

DrugInventory drugInventory = new DrugInventory("121212");
DrugInventory drugInventory1 = new DrugInventory("232323");
DrugInventory drugInventory2 = new DrugInventory("343434");
DrugInventory drugInventory3 = new DrugInventory("454545");
DrugInventory drugInventory4 = new DrugInventory("565656");

drugInventories.add(drugInventory);
drugInventories.add(drugInventory1);
drugInventories.add(drugInventory2);
drugInventories.add(drugInventory3);
drugInventories.add(drugInventory4);

List<Drug> drugs = new ArrayList<>();

Drug drug = new Drug("121212");
Drug drug1 = new Drug("232323");
Drug drug2 = new Drug("343434");

drugs.add(drug);
drugs.add(drug1);
drugs.add(drug2);

The expected result here should be equal to a list looking like this:

 [DrugInventory(inventoryId=454545, drugStatus=null), DrugInventory(inventoryId=565656, drugStatus=null)]

I can use nested loops here to compare each element but that would be inefficient. How can I do it efficiently?

Upvotes: 2

Views: 4539

Answers (3)

Srikanth Hugar
Srikanth Hugar

Reputation: 385

I can think of 2 solutions. One with extra space and another without extra space. It's trade of between space and time complexity, whichever best suits you. Sample code snippets below...

1. Sort Drugs by, and binary Search for each element of Drug Inventory(inventoryId).

    // Sort Drug by id
    Comparator<Drug> drugComparator = new Comparator<Drug>() {
        @Override
        public int compare(Drug d1, Drug d2) {
            return d1.id.compareTo(d2.id);
        }
    };

    Collections.sort(drugs, drugComparator);

    for (DrugInventory inventory : drugInventories) {
        if (!binarySearch(drugs, inventory.inventoryId)) {
            System.out.println(inventory.inventoryId);
        }
    }

    public static boolean binarySearch(List<Drug> drugs, String drugInventory) {

    int left = 0;
    int right = drugs.size() - 1;

    while (left <= right) {
        int middle = left + (right - left) / 2;
        int comapare = drugs.get(middle).id.compareTo(drugInventory);
        if (comapare == 0) {
            return true;
        } else if (comapare < 0) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return false;
}

2. Use HashSet add and remove the elements(id/inventoryId), remaining id's in set will be missing id's.

    Set<String> set = new HashSet<String>();

    // Add drug inventories to set
    for (DrugInventory inventoryElement : drugInventories) {
        set.add(inventoryElement.inventoryId);
    }

    // Remove drugs from set
    for (Drug drugElement : drugs) {
        set.remove(drugElement.id);
    }

    // Remaining entries in set are missing entries
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

Upvotes: 0

Thomas
Thomas

Reputation: 5094

For the specific problem of finding the drugs in inventory that do not exist in the drug list, you can use:

public static List<DrugInventory> findMissingDrugs(List<Drug> drugs, 
                                                   List<DrugInventory> inventory) {
    Set<String> drugIdLookup = drugs.stream()
                                    .map(d -> d.id)
                                    .collect(Collectors.toCollection(HashSet::new));
    return inventory.stream()
                    .filter(i->!drugIdLookup.contains(i.inventoryId))
                    .collect(Collectors.toList());      
}

First, we pull just the IDs into a HashSet (HashSet offers O(1) lookup time complexity), then we collect everything from inventory which isn't in that lookup set. If you have more complex lookups where you need to use multiple keys, then the other answer about restructuring both into HashMaps where the IDs are keys is a better long term approach.

Upvotes: 5

Marco Schmidt
Marco Schmidt

Reputation: 111

  • Create a Map<String, DrugInventory> and a Map<String, Drug>, e.g. using HashMap as implementation.
  • Add drug and drug inventory objects into the respective map with put using the id and inventoryId fields of each object as first and the object as second parameter.
  • Create a set of the combined key values of both maps using Map's keySet method.
  • Iterate over those keys and retrieve a drug and drug inventory object from the respective map. If both are non-null for a particular key you have a match and can print out the details in which you are interested with System.out.println.

Upvotes: 1

Related Questions