improving time efficiency of code

Question

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;
}

It is one of my assignments but I'm not sure how this can be simplified at all — user9599761
– user9599761, Commented Apr 5, 2018 at 1:35
Not clear whether these are linked lists, array lists or some other type. But you could look at the retainAll method of the LinkedList class or of the ArrayList class to see how it's done there. — Dawood ibn Kareem
– Dawood ibn Kareem, Commented Apr 5, 2018 at 1:42
Also, if you know that these two lists are sorted into an equivalent order, you can use that fact to speed up your algorithm. — Dawood ibn Kareem
– Dawood ibn Kareem, Commented Apr 5, 2018 at 1:49
It is a LinkedList class but I'm not sure I know what you mean by retainAll — user9599761
– user9599761, Commented Apr 5, 2018 at 1:52

I. Ahmed · Accepted Answer · 2018-04-05 02:51:33Z

2

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;
}

edited Apr 5, 2018 at 2:51

answered Apr 5, 2018 at 1:47

I. Ahmed

2,5261 gold badge14 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dawood ibn Kareem Over a year ago

You could just use HashSet instead of HashMap for this. Also, I think your if condition should be if (list1Map.get(list2.getItem(i)) == 1). Of course, if you change to a HashSet that would be if (list1Set.contains(list2.getItem(i))).

Jacob G. Over a year ago

There's no reason to have the redundant <LLList, Integer>; I'm not sure why you keep adding it back.

Collectives™ on Stack Overflow

improving time efficiency of code

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related