Maximum Gap Problem

[dev-AshishRanjan]

Is your feature request related to a problem? Please describe.

The question is :

Given an integer array nums, return the maximum difference between two 
successive elements in its sorted form. If the array contains less than two elements, 
return 0.
You must write an algorithm that runs in linear time and uses linear extra space.

Here the point to be noted is You must write an algorithm that runs in linear time and uses linear extra space

Describe the solution you'd like

The Approach is to use Radix Sort

Algorithm for Radix Sort

The idea of Radix Sort is to do digit by digit sort starting from least significant 
digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.

1. radixSort(arr) 
2. max = largest element in the given array 
3. d = number of digits in the largest element (or, max) 
4. Now, create d buckets of size 0 - 9 
5. for i -> 0 to d 
6. sort the array elements using counting sort (or any stable sort) according to 
the digits at the ith place

we are going to use the Counting Sort algorithm as a subroutine within the Radix Sort implementation. Radix Sort is a non-comparative sorting algorithm that sorts numbers by their digits. It performs counting sort for each digit position from the least significant digit to the most significant digit. In each iteration, the counting sort is applied to sort the numbers based on the current digit.

[Kumar-laxmi]

Please don't raise issues to solve problems from LeetCode, GFG or HackerRank