Best algorithm to find an element in an ordered list

Question

There is list A which contains numbers in ascending order.

Similarly a list B which also contains numbers in ascending order.

The result should be list C which contains numbers from A which are not in B.

My Solution:

I iterated through A and checked for the number in B using .contains() and added the required elements in C.

I was told using .contains() is higher order of complexity O(n).

Does anyone have a better solution?

Answer 1

Yes, your method will get O(n^2). The idea to get O(n) is just like merging two sorted lists into one. Merging two sorted lists into one is a Union. Finding common elements in two sorted lists is an Intersection. Your problem is to find the set difference of two sorted lists. Drawing a simple example on paper, you will find you can use two iterators to do it in O(n) time.