CODEWITHSUNDEEP
listsortingoptimizationtimeduplicates
akhil_mittal
akhil_mittal

Reputation: 24197

How to find the common elements in two lists? Best solution in terms of time complexity and space complexity

I have two lists and elements in each list is a employee object. Every employee has an id(int) and name (string) say.

Both the lists may have some common employees and those need to be given some special privilege. The task is to find those common ones.

One solution can be to use nested loops but that would be O(n^2). Another one can be to sort both of them on employee-id and that would be O(nlogn) and then using logic similar to merge. We traverse both of them simultaneously and when we find employee with same id we capture it. What is the best way to solve it?

Upvotes: 0

Views: 523

Answers (1)

Pandrei
Pandrei

Reputation: 4961

It sounds like you want to get the intersection of the two linked lists. For this you would have to first sort them O(nlogn), n being the size of the largest one. Then you build a list containing the common elements: start withe the head of the lists and advance the pointers according to employee ID.

if (list1.ID == list2.ID)
{
  copyToNewList(list1.ID);
}
else
if(list1.ID > list2.ID)
{
   lsit2 = list2->next;
}
else
{
  lsit1 = list1->next;
}

You have to consider the case when you finish going through one of the lists and the other one still has elements - but you get the idea.

If space is not your concern, and you are only worried about speed, you can allocate an array of size max ID you expect to have in any of the lists. In this array, each index will represent the ID. Now you can scan the first array and for each elements array[ID] = 1. Then you scan the second list and:

if (array[ID] == 1) array[ID] = 3; else array[ID] = 2; Now your array can tell you which elements are common, which are only in list 1 and which only in list 2 - if you need this info - in O(max(m,n));

Please mind that this solution will be efficient for a limited number of ID's - if you expect to have ID's in the order of tens or hundreds of thousands, not only will it be space inefficient, retrieving the data from the array will also take a long time.

Edit: Actually if you use a hash table instead of an array you get a more space efficient solution and it's still O(max(m,n))

Upvotes: 1

Related Questions