Missing Items
November 22, 2016
There are many ways to solve this problem. Here’s the worst:
(define (missing1 xs ys) (list-of x (x in xs) (not (member x ys))))
That’s a list comprehension that iterates over all the items in xs, doing a linear search for the corresponding item in ys, so it takes quadratic time. Better is to sort the two lists and scan them; the scan is linear but the sort is O(n log n), so the total time complexity is O(n log n):
(define (missing2 xs ys)
(let loop ((xs (sort < xs)) (ys (sort < ys)) (zs (list)))
(cond ((null? xs) zs)
((< (car xs) (car ys))
(loop (cdr xs) ys (cons (car xs) zs)))
((< (car ys) (car xs))
(loop xs (cdr ys) zs))
(else (loop (cdr xs) (cdr ys) zs)))))
The third possibility is to insert all the items of the second list in a hash table, then iterate through the items of the first list; each of those two operations is linear, so the entire time complexity is linear:
(define (missing3 xs ys)
(let ((h (make-hash (lambda (x) (modulo x 97)) = #f 97)))
(do ((ys ys (cdr ys))) ((null? ys))
(h 'insert (car ys) (car ys)))
(filter (lambda (x) (not (h 'lookup x))) xs)))
You can run the program at http://ideone.com/H5HCrN.
Programming Praxis 
My attempt at rewriting your sort and search in python… not sure how great it is.
def missing2(list1, list2): list1 = (sorted(list1)) list2 = (sorted(list2)) missing = [] y=0 for x in list1: # take item from list2 # if < x get another one # if = x we have a match (discard # if > x this number is missing from list2 print ("x " + str(x)) print("y was " + str(y)) while (y < x): y = list2.pop(0) # could still exist if y > x: # x is missing missing.append(x) else: #match print ("matched x " + str(x)) return(missing)@Simon W. Here some remarks that may improve your code. It is pretty good already. I see one difficulty: on line 14 you pop list2, but it is important to check if list2 is not empty. So line 13 should read: while list2 and y < x:. A small point is that you seem to like brackets. In lines 2, 3, 13, and 22 you can remove some. I hope this helps.
Method 2 and 3 in Python.
def missing3(a, b): setb = set(b) return [ai for ai in a if ai not in setb] def missing2(list1, list2): list1 = sorted(list1) list2 = sorted(list2) missing = [] while list1 and list2: if list1[0] <= list2[0]: x = list1.pop(0) if x < list2[0]: missing.append(x) else: list2.pop(0) return missing + list1@Paul: One advantage of Simon’s approach (with a check for an empty list2 added) is that it avoids checking both lists each time around the inner loop, so it will be somewhat more efficient (assuming the compiler doesn’t do anything very clever). Here’s one possibility:
def missing3(list1, list2): list1 = sorted(list1) if len(list2) == 0: return list1 list2 = sorted(list2) missing = [] while list1: x = list1[0] while list2[0] < x: list2.pop(0) if not list2: return missing + list1 if x < list2[0]: missing.append(x) list1.pop(0) return missing@Simon: I’ve just noticed that the @praxis missing2 solution doesn’t check for end of second list either, so you are in good company.
@matthew, @Simon W: Simon’s code with the empty check added, does not always work correctly (give the same results as my missing3). In my version I can cache list1[0] and list2[0], of course. Btw, it is faster to test the last element and pop from the high side and reverse the resulting missing list.
@Paul: Is my version up above correct? Can’t find any difference with your function. I’d be inclined to use indexes for something like this if performance really was an issue.
@Paul: could you please clarify why it doesn’t always work correctly with the empty check added? Many thanks
@Simon W: on ideone you find some code that tests your function. You can see there examples, that do not work. I see two problems. The first is probably some type of typo: your return statement is shifted two spaces to the right. After repairing that I see that your method does not work if the missing value has the highest value. So you should check when list2 is empty, if there are entries left in list1.
@matthew: your version is correct.
Thanks @Paul – much appreciated. I’ve decided to tackle a few of these problems a week to “sharpen my saw” and the input from yourself and @matthew is very helpful and appreciated
@Simon W: You are wellcome. One more advice: indent with 4 spaces; it makes the code easier to read.
Must my answers be in a specifc language?
You may use any language you like.
A Haskell version.
Isn’t this equivalent to the Set Difference operation?
Solution in Ruby using built-in stuff.
@V: It almost is. You have to list all the elements in a, which are not in b. If a=[1,1,2] and b=[2], the correct answer is [1,1] and a set difference gives [1].
Ahh I see. In that case just need to remove the uniq method.
function missingItems(xs, ys) { return xs.reduce(function(acc, elt) { ys.indexOf(elt) < 0 || acc.push(elt) return acc; }, []); } console.log(missingItems([5, 3, 12, 9, 8], [3, 9, 8]))Hi, I’d like to post my quick-hand solution,
i haven’t made full test, this code may be buggy,
hope for your comments & advices.
List list_1 = new List(5,15,2,20,30,40,8,1);
List list_2 = new List(2,20,15,30,1,40,0,8);
List answer = new List();
bool found = false;
foreach (int x in list_1)
{
foreach (int y in list_2)
{
if (x == y)
{
found = true;
break;
}
}
if (found)
{
answer.add(x);
found = false;
}
}