Find common elements in two sorted lists in linear time

Question

I have a sorted list of inputs:

let x = [2; 4; 6; 8; 8; 10; 12]
let y = [-8; -7; 2; 2; 3; 4; 4; 8; 8; 8;]

I want to write a function which behaves similar to an SQL INNER JOIN. In other words, I want to return the cartesian product of x and y which contains only items shared in both lists:

join(x, y) = [2; 2; 4; 4; 8; 8; 8; 8; 8; 8]

I've written a naive version as follows:

let join x y =
    [for x' in x do
        for y' in y do
            yield (x', y')]
    |> List.choose (fun (x, y) -> if x = y then Some x else None)

It works, but this runs in O(x.length * y.length). Since both my lists are sorted, I think its possible to get the results I want in O(min(x.length, y.length)).

How can I find common elements in two sorted lists in linear time?

Answer 1

I can't help you with the F#, but the basic idea is to use two indices, one for each list. Choose the item in each list at the current index for that list. If the two items are the same value, then add that value to your result set and increment both indices. If the items have different values, increment just the index for the list containing the lesser of the two values. Repeat the comparison until one of your lists is empty and then return the result set.