In this article, we are going to see the interesting solution to the problem - "Maximum Gap". This will involve the concept of Bucket Sort and Radix Sort.

Pre-requisites:

• Bucket Sort
• Radix Sort

Problem Statement

Find the maximum difference between two successive elements in a given integer array nums after sorting it in non-decreasing order. If the length of nums is less than two, the function should return 0.

Example 1:
Input: nums = [10, 5, 20]
Output: 10
Explanation: After sorting the array in non-decreasing order, we get [5, 10, 20]. The maximum difference between two successive elements is between 10 and 20, which is 10.

Example 2:
Input: nums = [2]
Output: 0
Explanation: Since the array contains less than two elements, the function should return 0.

Example 3:
Input: nums = [1, 1, 1, 1]
Output: 0
Explanation: After sorting the array in non-decreasing order, we get [1, 1, 1, 1]. Since all the elements are equal, the maximum difference between two successive elements is 0.

Approach

The brute force method will involve first sorting the algorithm and iterating through the array checking for maximum difference.
The optimized solution will involve the use of advanced non-comparison based algorithm like bucket sort or radix sort.

NAIVE APPROACH - INBUILT SORT

Since we want to find the maximum gap or difference between two successive elements. We would want our array to be sorted so that we check every consecutive difference. hence we apply inbuilt sorting to first sort the array. And then iterate over the array checking for maximum difference.

Algorithm

• Sort the array in non-decreasing order.
• Traverse the sorted array and find the maximum difference between two successive elements.

Implemented Code

class Solution {
    public int maximumGap(int[] nums) {
        if(nums.length<2) return 0;
        Arrays.sort(nums);
        int md = Integer.MIN_VALUE;
        for(int i=1;i<nums.length;i++){
            md=Math.max(md,nums[i]-nums[i-1]);
        }
        return md;      
    }

public static void main(String args[]){
int arr[]={10, 5, 20};
int ans = maximumGap(arr);
System.out.println(ans);
}
}

Time Complexity: O(nlogn)
Space Complexity: O(1)

Code Explained:

First we have checked for the base condition. if number of element in array is less than 2 we return zero.
Sort the array using inbuilt sort method, Arrays.sort().
Next we traversed the sorted array and continue finding the difference till we have achieved the maximum.

BUCKET SORT

To optimize the algorithm, we would want our sorting to be done in linear time. Hence we use bucket sort. It sort the arrays in linear time and then we can look for the maximum consecutive difference by iterating over the array.

Algorithm

1. Find the minimum and maximum elements in the array nums.
2. Calculate the bucket size as bucket_size = (max_element - min_element) / (n - 1) + 1, where n is the number of elements in nums.
3. Create n - 1 buckets of size bucket_size each. Each bucket will hold a range of elements based on the bucket size.
4. Traverse the array nums and put each element in the appropriate bucket based on its range.
5. Calculate the maximum and minimum element for each non-empty bucket.
6. Traverse the non-empty buckets and calculate the maximum difference between two successive buckets using the minimum element of the next bucket and the maximum element of the current bucket.
7. Return the maximum difference.

Implemented Code

public class Solution {
public int maximumGap(int[] nums) {
    int n = nums.length;
    if(n < 2) return 0;
    int min = nums[0];
    int max = nums[0];
    for(int i = 1;i < n;i++){
        if(min > nums[i]) min = nums[i];
        if(max < nums[i]) max = nums[i];
    }
    
    int gap = (max-min)/(n-1);
    if(gap == 0) gap++;
    int len = (max-min)/gap+1;
    int [] tmax = new int [len];
    int [] tmin = new int [len];
    
    for(int i = 0;i < n;i++){
        int index = (nums[i]-min)/gap;
        if(nums[i] > tmax[index]) tmax[index] = nums[i];
        if(tmin[index] == 0 || nums[i] < tmin[index]) tmin[index] = nums[i];
    }
    int myMax = 0;
    for(int i = 0;i < len;i++){
        if(myMax < tmin[i]-min) myMax = tmin[i]-min;
        if(tmax[i] != 0) min = tmax[i];
    }
    return myMax;
}
public static void main(String args[]){
int arr[]={10, 5, 20};
int ans = maximumGap(arr);
System.out.println(ans);
}
}

Time Complexity: O(n)
Space Complexity: O(n)

Code Explained
We first find the minimum and maximum elements in the array, calculates the gap size based on the array length, and creates buckets for the elements. Each bucket contains a range of elements based on the gap size. The maximum and minimum values in each bucket are calculated, and the maximum difference between two successive buckets is determined by comparing the minimum value of the current bucket with the maximum value of the previous bucket.

For example, given the array [1, 5, 9, 10],
gap size = (10-1)/(4-1) = 3
number of buckets= (10-1)/3+1 = 4
The code would find the maximum difference of 4 between 5 and 9.

RADIX SORT

To optimize the algorithm, we would want our sorting to be done in linear time. Hence we use radix sort. It sort the arrays in linear time and then we can look for the maximum consecutive difference by iterating over the array.

Algorithm

1. Find the maximum element in the array nums and count the number of digits in it. Let this number of digits be k.
2. Run a loop for k times starting from the least significant digit to the most significant digit.
3. For each iteration of the loop, perform the following steps:
4. Initialize a count array of size 10 with all elements set to 0. This count array will be used to keep track of the frequency of each digit.
5. Traverse the array nums and count the frequency of the current digit in the count array.
6. Update the count array such that each element represents the number of elements less than or equal to it.
7. Create a temporary array of the same size as nums and fill it with the sorted elements based on the current digit using the count array.
8. Copy the elements from the temporary array back to nums.
9. After the loop is complete, the array nums will be sorted in non-decreasing order. Traverse the sorted array nums and find the maximum difference between two successive elements.

Implemented Code

public class Solution {
public int maximumGap(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }
    int m = nums[0];
    for (int i = 1; i < nums.length; i++) {
        m = Math.max(m, nums[i]);
    }
    int exp = 1; 
    int R = 10; 
    int[] aux = new int[nums.length];
    while (m / exp > 0) { // traverse through all digits from LSB to MSB
        int[] count = new int[R];
        
        for (int i = 0; i < nums.length; i++) {
            count[(nums[i] / exp) % 10]++;
        }  
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            aux[--count[(nums[i] / exp) % 10]] = nums[i];
        }  
        for (int i = 0; i < nums.length; i++) {
            nums[i] = aux[i];
        }
        exp *= 10;
    }
    int max = 0;
    for (int i = 1; i < aux.length; i++) {
        max = Math.max(max, aux[i] - aux[i - 1]);
    }   
    return max;
    }

public static void main(String args[]){
int arr[]={10, 5, 20};
int ans = maximumGap(arr);
System.out.println(ans);
}
}

Time Complexity: O(n)
Space Complexity: O(n)

Code Explained
The code iterates through all digits from the least significant bit (LSB) to the most significant bit (MSB), sorting the elements of the array according to each digit. The variable m represents the maximum element in the array, and the variable exp represents the digit position currently being sorted.
The variable** aux** is used as a temporary array to store the sorted elements at each iteration of the loop. The code returns the maximum difference found between successive elements in the sorted array.

For example, array nums = {170, 45, 75, 90, 802, 24, 2, 66}. The algorithm will first find the maximum element in the array, which is 802. Then, it will iterate through all the digits from the least significant bit (LSB) to the most significant bit (MSB). In the first iteration, it will sort the elements according to the first digit from the right. The sorted elements will be {170, 90, 802, 2, 24, 45, 75, 66}. In the next iteration, we will sort the elements according to the second digit from the right. The sorted elements will be {2, 24, 45, 66, 75, 90, 170, 802}.

Finally, we will calculate the maximum difference between successive elements in the sorted array, which will be 802 - 170 = 632. This is the maximum gap between two successive elements in the original array.

Conclusion

We learnt to solve the problem Maximum gap by using brute force method of suing inbuilt sorting. And then used optimized sorting techniques like Bucket Sort and Radix Sort to solve the same problem in linear complexity time.