## 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 = []
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)
```
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 <= list2:
x = list1.pop(0)
if x < list2:
missing.append(x)
else:
list2.pop(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
while list2 < x:
list2.pop(0)
if not list2: return missing + list1
if x < list2: missing.append(x)
list1.pop(0)
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 and list2, 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

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

```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
=> 

[2, 1, 1, 2]. uniq - [1, 3, 5, 3, 1].uniq
=> 

```
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=, the correct answer is [1,1] and a set difference gives .

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]
=> 

[2, 1, 1, 2] - [1, 3, 5, 3, 1]
=> [2, 2]

[1,1,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,

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);
bool found = false;

foreach (int x in list_1)
{
foreach (int y in list_2)
{
if (x == y)
{
found = true;
break;
}
}

if (found)
{