CODEWITHSUNDEEP
java
user9599761
user9599761

Reputation:

improving time efficiency of code

How can this code be edited to improve the time efficienc?

public static LLList intersect(LLList list1, LLList list2) {
    LLList inters = new LLList();

    for (int i = 0; i < list1.length(); i++) {
        Object item1 = list1.getItem(i);
        for (int j = 0; j < list2.length(); j++) {
            Object item2 = list2.getItem(j);
            if (item2.equals(item1)) {
                inters.addItem(item2, inters.length());
                break;   // move onto the next item from list1
            }
        }
    }

    return inters;
}

Upvotes: 1

Views: 130

Answers (1)

I. Ahmed
I. Ahmed

Reputation: 2534

Solution In Question: You are using two for loop and comparing items of each list to other list item. As a result the solution is O(n^2).

Optimized solution: Instead of comparing you can use HashMap, then insert one lists items into it using O(n) complexity.

Then using a loop check whether the items present in HashMap, the second loop also have O(n) complexity.

So, the complexity of the solution will be O(N) + O(N).

Please check the final solution:

public static LLList intersect(LLList list1, LLList list2) {
    LLList inters = new LLList();

    Map<LLList, Integer> list1Map = new HashMap<>();

    for(int i = 0; i < list1.length; i++) {
       list1Map.put(list1.getItem(i), 1);
    }

    for(i = 0; i < list2.length; i++) {
       if(list1Map[list1.getItem(i)] == 1) {
          inters.addItem(list1.getItem(i)], inters.length());
       }
    }

    return inters;
}

Upvotes: 2

Related Questions