# Another pigeon hole sort solution

• ``````public class Solution {
public int maximumGap(int[] nums) {
if (nums.length<2){
return 0;
}
int min = Integer.MAX_VALUE;
int max = 0;
for (int num:nums){
if (num<min){
min = num;
}
if (num>max){
max = num;
}
}

int numPigeonHoles = nums.length+1;
int pigeonHoleSize = (int)Math.ceil((double)(max-min)/(double)numPigeonHoles);
if (pigeonHoleSize == 0){
pigeonHoleSize = 1;
}
numPigeonHoles = (max-min)/pigeonHoleSize+1;

PigeonHole[] pigeonHoles = new PigeonHole[numPigeonHoles];
for (int num:nums){
int pigeonHoleIndex = (num-min)/pigeonHoleSize;
PigeonHole pigeonHole = pigeonHoles[pigeonHoleIndex];
if (pigeonHole == null){
pigeonHole = new PigeonHole();
pigeonHoles[pigeonHoleIndex]=pigeonHole;
}
}

int maxDiff = 0;
int i = 1;
while (i<pigeonHoles.length-1){
PigeonHole end = pigeonHoles[i];
if (end == null){
PigeonHole start = pigeonHoles[i-1];
while(end == null){
end = pigeonHoles[++i];
}

int diff = end.min-start.max;
if (diff>maxDiff){
maxDiff = diff;
}
}
else{
i++;
}
}
return maxDiff;
}

class PigeonHole{
int min = Integer.MAX_VALUE;
int max = 0;