My Java Solution using RadixSort


  • 0
    R
    public class Solution {
        public int maximumGap(int[] nums) {
            if(nums.length < 2){
                return 0;
            }
            int size = nums.length;
            radixSort(nums, size);
            int answer = 0;
            for(int i = 1; i < size; i++){
                answer = Math.max(nums[i] - nums[i-1], answer);
            }
            return answer;
            
        }
        public static void radixSort(int[] nums, int size){
            int max = getMax(nums, size);
            for(int exp = 1; max/exp>0; exp *= 10){
                countSort(nums, size, exp);
            }
        }
    
        // Utility function to get max element in an array
        public static int getMax(int[] arr, int size){
            int max = arr[0];
            for(int i = 1; i < size; i++){
                max = Math.max(max, arr[i]);
            }
            return max;
        }
        
        //Subrotine function using Countsort to sort the elements
        public static void countSort(int[] arr, int size, int exp){
            int[] output = new int[size];
            int[] count = new int[10];
            Arrays.fill(count, 0);
    
            for(int i = 0; i < size; i++){
                count[(arr[i] / exp) % 10]++;
            }
    
            for(int i = 1; i < 10; i++){
                count[i] += count[i-1];
            }
    
            for(int i = size - 1; i >= 0; i--){
                output[count[(arr[i]/exp)%10] - 1] = arr[i];
                count[(arr[i]/exp)%10]--;
            }
            
            // Coping the output array to actual array
            for(int i = 0; i < size; i++){
                arr[i] = output[i];
            }
        }
    }

Log in to reply
 

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