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.


Pages: 1 2

20 Responses to “Missing Items”

  1. Simon W said

    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 = []
      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
          print ("matched x " + str(x))
  2. Paul said

    @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.

  3. Paul said

    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]:
        return missing + list1
  4. matthew said

    @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:
                if not list2: return missing + list1
            if x < list2[0]: missing.append(x)
        return missing
  5. matthew said

    @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.

  6. Paul said

    @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.

  7. matthew said

    @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.

  8. Simon W said

    @Paul: could you please clarify why it doesn’t always work correctly with the empty check added? Many thanks

  9. Paul said

    @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.

  10. Paul said

    @matthew: your version is correct.

  11. Simon W said

    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

  12. Paul said

    @Simon W: You are wellcome. One more advice: indent with 4 spaces; it makes the code easier to read.

  13. Must my answers be in a specifc language?

  14. programmingpraxis said

    You may use any language you like.

  15. Globules said

    A Haskell version.

    import Data.List.Ordered (minus, nubSort)
    omit :: Ord a => [a] -> [a] -> [a]
    omit xs ys = nubSort xs `minus` nubSort ys
    main :: IO ()
    main = do
      print $ [5, 15, 2, 20, 30, 40, 8, 1] `omit` [2, 20, 15, 30, 1, 40, 0, 8]
      -- Duplicates are handled, too.
      print $ [2, 1, 1, 2] `omit` [1, 3, 5, 3, 1]
    $ ./missing 
  16. V said

    Isn’t this equivalent to the Set Difference operation?

    Solution in Ruby using built-in stuff.

    [5, 15, 2, 20, 30, 40, 8, 1].uniq  - [2, 20, 15, 30, 1, 40, 0, 8].uniq 
    => [5]
    [2, 1, 1, 2]. uniq - [1, 3, 5, 3, 1].uniq
    => [2]
  17. Paul said

    @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].

  18. V said

    Ahh I see. In that case just need to remove the uniq method.

    [5, 15, 2, 20, 30, 40, 8, 1] - [2, 20, 15, 30, 1, 40, 0, 8]
    => [5]
    [2, 1, 1, 2] - [1, 3, 5, 3, 1]
    => [2, 2]
    [1,1,2] - [2]
    => [1, 1]
  19. vyusfire said
    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.

  20. West said

    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;

    if (found)
    found = false;

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: