CODEWITHSUNDEEP
algorithmlistmath
Raúl Reguillo Carmona
Raúl Reguillo Carmona

Reputation: 395

List intersection with O(n·m)

Suppose we have two lists of lengths n and m respectively: 

val l1 = Seq(1,2,3,4,5,6,7,8,9,0)
val l2 = Seq(2,4,6,8,10,12)

Is there a way to calculate their intersection wiht less than O(n·m)?

That is

val result = Seq(2,4,6,8)

EDIT: we can assume our lists are sorted.

Upvotes: 0

Views: 117

Answers (2)

Chase R Lewis
Chase R Lewis

Reputation: 2307

  1. Put one of the items into a hash set. O(min(n,m))

    var set2 = new HashSet<int>(){2,4,6,8,10,12};

  2. Take the other set and check if it exists in hash set. Each access is O(1) since we need the other set and we created the hash set with the shorter set that means the time is O(max(m,n)) if it return true in the other set add it to your results.

  3. Result is O(n+m) in time and O(min(n,m)) in memory.

Upvotes: 2

Avishek Bhattacharya
Avishek Bhattacharya

Reputation: 6974

For sorted lists the following Algorithm should work:

You can have 2 pointers say (i and j) one at l1 another at l2.

Now you can iterate on l1 and l2 such that 

 while (i< l1.size && j < l2.size ) {
    if l1[i] < l2[j] 
       i++ 
    else if (l1[i] == l2[j] )
       i++; j++; output = output U {l1[i]}
    else
       j++  
 }

This should be in O(max(m,n))

Upvotes: 2

Related Questions