Another pigeon hole sort solution


  • 0
    Q
    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;
                }
                pigeonHole.add(num);
            }
            
            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;
            void add(int val){
                if (val <min){
                    min = val;
                }
                if (val >max){
                    max=val;
                }
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.