I need a function that checks two arrays for common elements faster, than O(size1*size2)

Question

I have that function and it's too long for me (O(n*m)). I need make it faster. Help pls.

bool obs(int a[],int n,int b[],int m){     //2 arrays with sizes
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(a[i]==b[j])
                return true;
    return false;
}

What's asked here is really testing basic knowledge and understanding of computer science and algorithms. If you don't know the answer, a bare code dump that implements this will not really help you to understand anything, or learn anything. Instead, the correct answer here should be to go and learn the relevant areas of computer science and algorithms which are needed to implement this. Unfortunately, stackoverflow.com is not a replacement for a [good C++ and computer science algorithms textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, Oct 16 '20 at 13:44
How do you know that your code is too slow? Are you guessing or did you measure it? Don't optimize if you are just guessing. There are tools to compare execution times (e.g. https://quick-bench.com) - but you might want to test in your own environment. — Simon Kraemer, Oct 16 '20 at 14:16

score 3 · Answer 1 · answered Oct 16 '20 at 13:45

Sort the arrays -> O(N logN) (with N = max(size A, size B) (faster sorting might be possible)

Then start with iterators to begin of both. Increment the iterator that points to the smaller element. You are done when you either reach the end or the iterators point to the same value. -> O(N)

In total: O(N logN)

I need a function that checks two arrays for common elements faster, than O(size1*size2)

1 Answers1