Min-Min-Max

August 12, 2016

Our straight forward solution calls library functions to get the minimum and maximum, then increments the minimum until it finds a number not in the input:

(define (min-min-max xs)
  (let loop ((m (+ (apply min xs) 1)))
    (if (member m xs)
        (loop (+ m 1))
        (values (apply min xs) m (apply max xs)))))
> (min-min-max '(-1 4 5 -23 24))
-23
-22
24

We’ll ignore the redundant calculation of the minimum.

Our second solution inserts each integer into a distinct priority queue (so we can ignore the problem of duplicates), then pops the priority queue for the minimum, then pops the priority queue repeatedly until it finds two non-consecutive integers, and finally pops the priority queue until it is exhausted to find the maximum:

(define (min-min-max xs)
  (let loop ((xs xs) (dpq (make-dpq <)))
    (if (pair? xs) (loop (cdr xs) (dpq-insert (car xs) dpq))
      (let ((m1 (dpq-first dpq)) (prev (dpq-first dpq)))
        (let loop ((dpq (dpq-rest dpq)))
          (if (= (+ prev 1) (dpq-first dpq))
              (loop (dpq-rest dpq))
              (let ((m2 (+ prev 1)))
                (let loop ((prev (dpq-first dpq)) (dpq (dpq-rest dpq)))
                  (if (dpq-empty? dpq)
                      (values m1 m2 prev)
                      (loop (dpq-first dpq) (dpq-rest dpq)))))))))))
> (min-min-max '(-1 4 5 -23 24))
-23
-22
24

I’m not sure that’s better. The original is O(n) if you implement member as an O(1) operation, but the “improved” version is O(n log n). At least we were able to use the distinct priority queue of the previous exercise.

You can run the program at http://ideone.com/aa6FIq.

Pages: 1 2

10 Responses to “Min-Min-Max”

  1. I think my naive perl queue version is similar to your second solution…

    print join "\t", mmm( qw(-1 4 5 -22 -23 24) ),"\n";
    
    sub mmm {
      my %F =  map { $_ => 1 } @_;
      my @Q = sort {$a <=> $b} keys %F;
      my $X = my $Y = shift @Q;
      $X++ while exists $F{$X};
      return ($Y,pop @Q,$X);
    }
    
    
  2. Rainer said
    with data (elem) as (values 
    (-1),(4),(5),(-23),(24))    
    select p.elem               
    from   data p               
    exception join data s       
    on     p.elem + 1 = s.elem 
    
  3. Daniel said

    Here’s a solution in Java.

    The first solution sorts the array, getting min and max from the ends, and looping over the array to find the smallest number between the two array bounds that is not in the array.

    The second solution is not particularly creative. It loops over the array, finding the min and max elements, and creating a hash set of array elements. Then it loops over a range from min to max to find the smallest number between the two array bounds that is not in the array.

    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.Set;
    
    public class MinMinMax {
      public static class Result {
        public Integer min = null;
        public Integer minAbsent = null;
        public Integer max = null;
        public String toString() {
          return String.format("min: %d; min absent; %d, max; %d", min, minAbsent, max);
        }
      }
      
      public static Result minMinMax1(int[] array) {
        Result result = new Result();
        if (array.length == 0) return result;
        int[] sorted = Arrays.copyOf(array, array.length);
        Arrays.sort(sorted);
        result.min = sorted[0];
        result.max = sorted[sorted.length - 1];
        for (int i = 1; i < sorted.length; ++i) {
          if (sorted[i-1] + 1 == sorted[i]) continue;
          result.minAbsent = sorted[i-1] + 1;
          break;
        }
        return result;
      }
      
      public static Result minMinMax2(int[] array) {
        Result result = new Result();
        if (array.length == 0) return result;
        Set<Integer> elements = new HashSet<>();
        for (int i = 0; i < array.length; ++i) {
          elements.add(array[i]);
          if (i == 0) {
            result.min = result.max = array[0];
            continue;
          }
          result.min = Math.min(result.min, array[i]);
          result.max = Math.max(result.max, array[i]);
        }
        for (int i = result.min + 1; i < result.max; ++i) {
          if (elements.contains(i)) continue;
          result.minAbsent = i;
          break;
        }
        return result;
      }
      
      public static void main(String[] args) {
        int[] array = {-1, 4, 5, -23, 24};
        
        Result result1 = minMinMax1(array);
        System.out.printf("minMinMax1\n%s\n", result1);
    
        Result result2 = minMinMax2(array);
        System.out.printf("\nminMinMax2\n%s\n", result2);
        
      }
    }
    

    Output:

    minMinMax1
    min: -23; min absent; -22, max; 24
    
    minMinMax2
    min: -23; min absent; -22, max; 24
    
  4. Rainer said

    Sorry, should be this:

    with data (elem) as (values                                         
    (-1),(4),(5),(-23),(24))                                            
    select min(p.elem) as minimum, max(p.elem) as maximum,              
           min(case when s.elem is null then p.elem + 1 else 99999 end) 
           as minimum_missing                                           
    from   data p                                                       
    left   outer join data s                                            
    on     p.elem + 1 = s.elem                                          
    
    ==>
    
    MINIMUM         MAXIMUM   MINIMUM_MISSING
         23-             24               22-
    
  5. Daniel said

    My last solution was not particularly creative. Here’s a bash script that solves the problem.

    #!/usr/bin/env bash
    
    read -d '' DATA <<"EOF"
    -23
    -1
    4
    5
    24
    EOF
    
    SORTED="$(echo "${DATA}" | sort -n)"
    
    echo -n "min: "
    echo "${SORTED}" | head -1
    
    echo -n "min absent: "
    echo "${SORTED}" | awk '$1!=prev+1 && NR>1 {print prev+1; exit} {prev=$1}'
    
    echo -n "max: "
    echo "${SORTED}" | tail -1
    
    
    min: -23
    min absent: -22
    max: 24
    
  6. Daniel said

    In my last post, my code was mistakenly reading in the data already sorted. Here’s the corrected version.

    #!/usr/bin/env bash
    
    read -d '' DATA <<"EOF"
    -1
    4
    5
    -23
    24
    EOF
    
    SORTED="$(echo "${DATA}" | sort -n)"
    
    echo -n "min: "
    echo "${SORTED}" | head -1
    
    echo -n "min absent: "
    echo "${SORTED}" | awk '$1!=prev+1 && NR>1 {print prev+1; exit} {prev=$1}'
    
    echo -n "max: "
    echo "${SORTED}" | tail -1
    

    Output:

    min: -23
    min absent: -22
    max: 24
    
  7. Milbrae said

    My two cents in D…

    import std.algorithm;
    import std.stdio;
    
    void main()
    {
        int[] data = [-1, 4, 5, -23, 24];
    
        mmm(data).writeln;
    }
    
    auto mmm(T)(ref T[] data)
    {
        if (data.length < 3) {
            return [-1, -1, -1];
        }
    
        data.sort();
        T len = data.length - 1, mini = data[0], maxi = data[len];
    
        for (uint k = 1; k < len; k++) {
            if ((mini + 1) != data[k]) return [mini, mini + 1, maxi];
        }
    
        return [0, 0, 0];
    }
    

    Output:
    [-23, -22, 24]

  8. Mike said

    Powershell…

    #build array
    $array = @(-1, 4, 5, -23, 24)
    #sort array
    $sarray = $array | sort
    #first element of array – smallest
    $sarray[0]
    #use array count to find last element of array – largest
    $sarrayc = $sarray.Count – 1
    #last element of array
    $sarray[$sarrayc]
    #use for loop to count up from smallest number
    for($i = $sarray[0];$i -le $sarray[$sarrayc];$i++)
    {

    #loop over each number is sorted array
    foreach($num in $sarray)
    {
    #if the count equals a number in the array break
    if($i -eq $num)
    {
    break
    }

    }
    #if the counter doesn’t equal a number in the array break
    if($i -ne $num)

    {
    #print the counter #
    write-host $i
    break

    }

    }

  9. kodejuice said

    JAVASCRIPT:

    function minMinMax(arr){
    var max = Math.max.apply(this, arr),
    min = Math.min.apply(this, arr),
    minAbsent = min;
    
    while(arr.indexOf(minAbsent)>-1 && minAbsent<max){
    minAbsent += 1;
    }
    
    return [min, minAbsent, max];
    }
    
    minMinMax([-1, 4, 5, -23, 24]); //=> [-23, -22, 24]
    
  10. r. clayton said

    Three solutions in Racket. The straightforward one uses sorting, the creative one uses a hash table like (almost) everybody else, and the other creative one uses a priority queue.

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 )

Google photo

You are commenting using your Google 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: