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.

Answer 2

O(min(n,m)) time is impossible: Take two lists [x;x;...;x;y] and [x;x;...;x;z]. You have to browse both lists till the end to compare y and z.

Even O(n+m) is impossible. Take [1,1,...,1] - n times and [1,1,...,1] - m times Then the resulting list should have n*m elements. You need at least O(n m) (correctly Omega(n m)) time do create such list.

Without cartesian product (simple merge), this is quite easy. Ocaml code (I don't know F#, should be reasonably close; compiled but not tested):

let rec merge a b = match (a,b) with
   ([], xs) -> xs
|  (xs, []) -> xs
|  (x::xs, y::ys) -> if x <= y then x::(merge xs (y::ys))
                else y::(merge (x::xs) (y::ys));;

(Edit: I was too late)

So your code in O(n m) is the best possible in worst case. However, IIUIC it performs always n*m operations, which is not optimal.

My approach would be

1) write a function

group : 'a list -> ('a * int) list

that counts the number of same elements:

group [1,1,1,1,1,2,2,3] == [(1,5);(2,2);(3,1)]

2) use it to merge both lists using similar code as before (there you can multiply those coefficients)

3) write a function

ungroup : ('a * int) list -> 'a list

and compose those three.

This has complexity O(n+m+x) where x is the length of resulting list. This is the best possible up to constant.

Edit: Here you go:

let group x =
  let rec group2 l m =
    match l with
    | [] -> []
    | a1::a2::r when a1 == a2 -> group2 (a2::r) (m+1)
    | x::r -> (x, m+1)::(group2 r 0)
  in group2 x 0;;

let rec merge a b = match (a,b) with
   ([], xs) -> []
|  (xs, []) -> []
|  ((x, xm)::xs, (y, ym)::ys) -> if x == y then (x, xm*ym)::(merge xs ys)
                           else  if x <  y then merge xs ((y, ym)::ys)
                                           else merge ((x, xm)::xs) ys;;

let rec ungroup a =
  match a with
    [] -> []
  | (x, 0)::l -> ungroup l
  | (x, m)::l -> x::(ungroup ((x,m-1)::l));;

let crossjoin x y = ungroup (merge (group x) (group y));;



# crossjoin [2; 4; 6; 8; 8; 10; 12] [-7; -8; 2; 2; 3; 4; 4; 8; 8; 8;];;
- : int list = [2; 2; 4; 4; 8; 8; 8; 8; 8; 8]

Answer 3

I don't know F#, but I can provide a functional Haskell implementation, based on the algorithm outlined by tvanfosson (further specified by Lasse V. Karlsen).

import Data.List

join :: (Ord a) => [a] -> [a] -> [a]
join l r = gjoin (group l) (group r)
  where
    gjoin [] _ = []
    gjoin _ [] = []
    gjoin l@(lh@(x:_):xs) r@(rh@(y:_):ys)
      | x == y    = replicate (length lh * length rh) x ++ gjoin xs ys
      | x < y     = gjoin xs r
      | otherwise = gjoin l ys

main :: IO ()
main = print $ join [2, 4, 6, 8, 8, 10, 12] [-7, -8, 2, 2, 3, 4, 4, 8, 8, 8]

This prints [2,2,4,4,8,8,8,8,8,8]. I case you're not familiar with Haskell, some references to the documentation:

• group
• length
• replicate

Answer 4

The problem with what he wants is that it obviously has to re-traverse the list.

In order to get 8,8,8 to show up twice, the function has to loop thru the second list a bit. Worst case scenario (two identical lists) will still yield O(x * y)

As a note, this is not utilizing external functions that loop on their own.

for (int i = 0; i < shorterList.Length; i++)
{
    if (shorterList[i] > longerList[longerList.Length - 1])
        break;
    for (int j = i; j < longerList.Length && longerList[j] <= shorterList[i]; j++)
    {
        if (shorterList[i] == longerList[j])
            retList.Add(shorterList[i]);
    }
}

Answer 5

The following is also tail-recursive (so far as I can tell), but the output list is consequently reversed:

let rec merge xs ys acc =
    match (xs, ys) with
    | ((x :: xt), (y :: yt)) ->
        if x = y then
            let rec count_and_remove_leading zs acc =
                match zs with
                | z :: zt when z = x -> count_and_remove_leading zt (acc + 1)
                | _ -> (acc, zs)
            let rec replicate_and_prepend zs n =
                if n = 0 then
                    zs
                else
                    replicate_and_prepend (x :: zs) (n - 1)
            let xn, xt = count_and_remove_leading xs 0
            let yn, yt = count_and_remove_leading ys 0
            merge xt yt (replicate_and_prepend acc (xn * yn))
        else if x < y then
            merge xt ys acc
        else
            merge xs yt acc
    | _ -> acc

let xs = [2; 4; 6; 8; 8; 10; 12]
let ys = [-7; -8; 2; 2; 3; 4; 4; 8; 8; 8;]
printf "%A" (merge xs ys [])

Output:

[8; 8; 8; 8; 8; 8; 4; 4; 2; 2]

Note that, as sdcvvc says in his answer, this is still O(x.length * y.length) in worst case, simply because the edge case of two lists of repeating identical elements would require the creation of x.length * y.length values in the output list, which is by itself inherently an O(m*n) operation.

Answer 6

I think this is O(n) on the intersect/join code, though the full thing traverses each list twice:

// list unique elements and their multiplicity (also reverses sorting)
// e.g. pack y = [(8, 3); (4, 2); (3, 1); (2, 2); (-8, 1); (-7, 1)]
// we assume xs is ordered
let pack xs = Seq.fold (fun acc x ->
    match acc with
    | (y,ny) :: tl -> if y=x then (x,ny+1) :: tl else (x,1) :: acc
    | [] -> [(x,1)]) [] xs

let unpack px = [ for (x,nx) in px do for i in 1 .. nx do yield x ]

// for lists of (x,nx) and (y,ny), returns list of (x,nx*ny) when x=y
// assumes inputs are sorted descending (from pack function)
// and returns results sorted ascending
let intersect_mult xs ys =
    let rec aux rx ry acc =
        match (rx,ry) with
        | (x,nx)::xtl, (y,ny)::ytl -> 
            if x = y then aux xtl ytl ((x,nx*ny) :: acc)
            elif x < y then aux rx ytl acc
            else aux xtl ry acc
        | _,_ -> acc
    aux xs ys []

let inner_join x y = intersect_mult (pack x) (pack y) |> unpack

Now we test it on your sample data

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

> inner_join x y;;
val it : int list = [2; 2; 4; 4; 8; 8; 8; 8; 8; 8]

EDIT: I just realized this is the same idea as the earlier answer by sdcvvc (after the edit).

Answer 7

I think it can be done simply by using hash tables. The hash tables store the frequencies of the elements in each list. These are then used to create a list where the frequency of each element e is frequency of e in X multiplied by the frequency of e in Y. This has a complexity of O(n+m).

(EDIT: Just noticed that this can be worst case O(n^2), after reading comments on other posts. Something very much like this has already been posted. Sorry for the duplicate. I'm keeping the post in case the code helps.)

I don't know F#, so I'm attaching Python code. I'm hoping the code is readable enough to be converted to F# easily.

def join(x,y):
    x_count=dict() 
    y_count=dict() 

    for elem in x:
     x_count[elem]=x_count.get(elem,0)+1
    for elem in y:
     y_count[elem]=y_count.get(elem,0)+1

    answer=[]
    for elem in x_count:
     if elem in y_count:
      answer.extend( [elem]*(x_count[elem]*y_count[elem] ) )
    return answer

A=[2, 4, 6, 8, 8, 10, 12]
B=[-8, -7, 2, 2, 3, 4, 4, 8, 8, 8]
print join(A,B)

Answer 8

You can't get O(min(x.length, y.length)), because the output may be greater than that. Supppose all elements of x and y are equal, for instance. Then the output size is the product of the size of x and y, which gives a lower bound to the efficiency of the algorithm.

Here's the algorithm in F#. It is not tail-recursive, which can be easily fixed. The trick is doing mutual recursion. Also note that I may invert the order of the list given to prod to avoid unnecessary work.

let rec prod xs ys = 
    match xs with
    | [] -> []
    | z :: zs -> reps xs ys ys
and reps xs ys zs =
    match zs with
    | [] -> []
    | w :: ws -> if  xs.Head = w then w :: reps xs ys ws
                 else if xs.Head > w then reps xs ys ws
                 else match ys with
                      | [] -> []
                      | y :: yss -> if y < xs.Head then prod ys xs.Tail else prod xs.Tail ys

The original algorithm in Scala:

def prod(x: List[Int], y: List[Int]): List[Int] = x match {
  case Nil => Nil
  case z :: zs => reps(x, y, y)
}

def reps(x: List[Int], y: List[Int], z: List[Int]): List[Int] = z match {
  case w :: ws if x.head == w => w :: reps(x, y, ws)
  case w :: ws if x.head > w => reps(x, y, ws)
  case _ => y match {
    case Nil => Nil
    case y1 :: ys if y1 < x.head => prod(y, x.tail)
    case _ => prod(x.tail, y)
  }
}