find the longest intersection of two integer arrays

Question

I have this problem but don't know what's best way to solve it in term of time complexity and space complexity. Suppose I have two integer arrays

   a={1,2,3,4,5}
   b={2,3,4,5,6}

and of course they not necessarily to be sorted.

So the question is how to find 2,3,4,5? It better to have some code. Thanks in advance

Answer 1

why do we need DP here? question says find the longest intersection, not any intersection. am i missing a point?

There are lot of solutions to this.

int [] a = {...}; // n elements  
int [] b = {...}; // m elements  

You can store one array in a dictionary and for each element in the other array check the dictionary. That O(n). THis will cost you more space due to dictionary. and it s not in-place

Another solution would be for each element in a, you can do a linear search on b. which is O(n.m)

Another would be ;if you sort both of the arrays. Then for each element in one array do a binary search in another array. You will find the intersection of two. and this will be mlogn + nlogn or nlogm + mlogm

do we really need DP here?

Answer 2

This is actually a pretty popular programming problem. There is a dynamic programming approach to solving it. You can check out more about it at http://en.wikipedia.org/wiki/Longest_common_subsequence_problem