## Min-Min-Max

### August 12, 2016

My statistics always decline in the summer, but they are starting to pick up, so I guess school must be starting in some places. Here’s a simple homework problem for beginning programmers:

Given an unsorted array of integers, find the smallest number in the array, the largest number in the array, and the smallest number between the two array bounds that is not in the array. For instance, given the array [-1, 4, 5, -23, 24], the smallest number is -23, the largest number is 24, and the smallest number between the array bounds is -22. You may assume the input is well-formed.

Your task is to provide two solutions to the problem, the first a straight forward solution that a beginning programmer might write, and a second solution that is rather more “creative;” feel free to define creative however you wish. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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) {
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

-23
-1
4
5
24
EOF

SORTED="\$(echo "\${DATA}" | sort -n)"

echo -n "min: "

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

-1
4
5
-23
24
EOF

SORTED="\$(echo "\${DATA}" | sort -n)"

echo -n "min: "

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.