# min missing max

Write a function accepting an integer list l and returning a triple (a b c) such that a is the smallest element in l, c is the largest element in l, and b is the smallest element not in l such that a < b < c.

``` \$ cat mmm.rkt
#lang racket

(require rnrs/sorting-6 rackunit "utl.rkt" "priority-queue.rkt")

(define (ht-min-missing-max l)

; Given the unsorted list of integers l, return the
; triple (mn sm mx) such that mn is the smallest
; integer in l, mx is the largest integer in l and
; sm is the smallest integer strictly between mn and mx
; not in l.  If there's no such integer, sm is undefned.
; If there's no such triple, return is undefined.

(define (smallest-missing mn mx ht)

; Given the sorted integer vector v, return the
; smallest integer strictly between v's min and max
; elements not in v.  Return undefined if there's
; no such integer.

(let loop ((i (+ mn 1)))
(when (< i mx)
(if (hash-has-key? ht i)
(loop (+ i 1))
i))))

(let*

((e (car l))
(ht (make-hash (list (cons e #t)))))

(let loop ((l (cdr l)) (mn e) (mx e))
(if (null? l)
(list mn (smallest-missing mn mx ht) mx)
(let ((e (car l)))
(hash-set! ht e #t)
(loop (cdr l) (min mn e) (max mx e)))))))

(define (pq-min-missing-max l)

; Given the unsorted list of integers l, return the
; triple (mn sm mx) such that mn is the smallest
; integer in l, mx is the largest integer in l and
; sm is the smallest integer strictly between mn and mx
; not in l.  If there's no such integer, sm is undefned.
; If there's no such triple, return is undefined.

(define (smallest-missing-element! min-q)

; Given the minimum priority queue min-q, return the
; smallest integer strictly between min-q's min and max
; elements not in min-q.  Code assumes such an integer
; exists.

(let loop ((min-e (pq-dq! min-q)))
(let ((next-min-e (+ min-e 1)))
(if (= next-min-e (pq-dq! min-q))
(loop next-min-e)
next-min-e))))

(define (largest-element! min-q)

; Return the largest element in the given the minimum
; priority queue min-q Code assumes such an element
; exists.

(let loop ((le (pq-dq! min-q)))
(if (pq-empty? min-q)
le
(loop (pq-dq! min-q)))))

(let*

((min-q (pq-new < l))
(min (pq-top min-q))
(sme (smallest-missing-element! min-q)))

(list min sme (largest-element! min-q))))

(define (sorted-min-missing-max l)

; Given the unsorted list of integers l, return the
; triple (mn sm mx) such that mn is the smallest
; integer in l, mx is the largest integer in l and
; sm is the smallest integer strictly between mn and mx
; not in l.  If there's no such integer, sm is undefned.
; If there's no such triple, return is undefined.

(define (missing-min v)

; Given the sorted integer vector v, return the
; smallest integer strictly between v's min and max
; elements not in v.  Return undefined if there's
; no such integer.

(let ((n (vector-length v)))
(let loop ((i 1) (mm (+ (vector-ref v 0) 1)))
(when (< i n)
(let ((e (vector-ref v i)))
(if (= e mm)
(loop (+ i 1) (+ e 1))
mm))))))

(unless (null? l)
(let ((v (vector-sort < (list->vector l))))
(list (vector-ref v 0)
(missing-min v)
(vector-ref v (- (vector-length v) 1))))))

(let ((in '(-1 4 5 -23 24))
(out '(-23 -22 24)))
(for-each
(lambda (f) (check-equal? (f in) out))
(list sorted-min-missing-max ht-min-missing-max pq-min-missing-max)))

(define (chopped-permuted-iota n)
(let loop ()
(let* ((l (permuted-iota n))
(a (car l))
(min-ab (min a b)))
(if (or (= min-ab 0) (= (max a b) (- n 1)))
(loop)
(values min-ab (cddr l))))))

(define (run-test iters l-size f)
(let loop ((i 0))
(when (< i iters)
(let-values (((mn l) (chopped-permuted-iota l-size)))
(check-equal? (f l) (list 0 mn (- l-size 1)))
(loop (+ i 1))))))

(run-test 100 20 sorted-min-missing-max)
(run-test 100 20 ht-min-missing-max)
(run-test 100 20 pq-min-missing-max)

(define (time-it f N l)
(let loop ((t 0) (n N))
(if (= n 0)
(round (/ t N))
(let-values
(((a b c d) (time-apply f (list l))))
(loop (+ t b) (- n 1))))))

(define (time n l)
(printf "~a  ~a  ~a  ~a\n"
(length l)
(time-it sorted-min-missing-max n l)
(time-it ht-min-missing-max n l)
(time-it pq-min-missing-max n l)
))

(define N 20)

(printf "n  sorted  hash table  priority queue\n" )
(do ((i 100002 (+ i 100000))) ((> i 500002))
(let-values (((mn l) (chopped-permuted-iota i)))
(time N l)))

\$ mzscheme mmm.rkt
n  sorted  hash table  priority queue
100000  54  50  200
200000  120  121  421
300000  191  187  661
400000  257  327  917
500000  333  404  1174

\$
```