Given two sorted lists, how to find elements that appear in list1 but not in list2?

Question

I was asked this question in an interview.

For example, if given list1: 1,1,2,4,5,7 and list2: 1,3,5,8 we should return a list3: 2,4,7.

The problem requires constant space, and we need to reduce the time complexity as much as possible.

Answer 1

We just walk through both lists at the same time -- using two "pointers" into them -- comparing the current two elements.

• When the first list's current element is less then the second's, we copy the first list's current element at the result's end and advance the first pointer.

• When the first list's current element is bigger than the second's, we advance the second pointer.

• When they are equal, we advance the first pointer.

Stop when the first pointer reaches the end of list. If the second pointer does this first, also copy all the remaining elements in list1 at the result's end one-by-one, or -- if these are singly linked lists and shared structure is allowed -- point the result's end pointer at the first pointer's value.

Assuming the result is a linked list, or other data structure with O(1) add-at-end operation, this gives us complexity of O(n+m) where n, m are the two lists' lengths.

This operation is otherwise known as set difference list1 \ list2 or relative set complement of list2 with respect to list1.

The two pointers used constitute the constant auxiliary space used by the algorithm.