Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

 Example:

Input: [12,3,9,1,17]
Output: 6
Explanation: The sorted form of the array is [1,3,9,12,17], (3,9) has the maximum difference 3.

Approach: We can sort the array and then in one traversal we can get the answer but this will take O(nlogn) time. Let's see how we can do better. Here is the problem we are trying to solve -

"Sorting requires comparing each element with every other element. Can we do it without it? It's possible if we somehow divide the elements in buckets and then just compare these buckets."

We can use Pigeonhole Sort technique to get it in Linear time. Remember here we are not trying to sort the array so we can reduce the number of buckets that means one bucket may contain more than one element. Here are few clarifications or pre-calculations before jumping to algorithm -

1. Gaps between the elements: Best case where all elements of the array are sorted and have a uniform gap between them. This means every adjacent pair of elements differ by the same constant. So for n elements, there are n-1 gaps.
2. Size of bucket: With n - 1 gaps and the range of numbers as max(array) -  min(array), we can say the size of bucket will be (max(array) -  min(array)) / n - 1 (approximately, could be ceil of the division).
3. No comparison among the elements in the bucket: We just can't compare each and every element in the bucket otherwise the time complexity will be high so what we can do? We only compare among buckets as the buckets can be already ordered but if we only compare buckets then we need to ensure that the gap between the buckets itself represent the maximal gap in the input array. 
• See the bucket size is (max - min)/(n-1) (point 2). Since the gaps within the same bucket would only be <= bucket size, we can say that the maximal gap would indeed occur only between two adjacent buckets.
4. How to compare two adjacent buckets: By comparing buckets' boundaries. We compare the minimum element of the next bucket to the maximum element of the current bucket.

Now let's talk about the algorithm, after discussing the above points, it is fairly straight forward -

We choose a bucket size b such that 1 < b ≤(max−min)/(n−1). Let's just choose b = Ceil((max - min)/(n-1)).
Thus all the n elements would be divided among numBuckets = (max - min)/b.
Hence the ith bucket would hold the range of values: (min + (i - 1) * b) to  (min + i * b).
Index of the bucket to which a particular element num belongs is given by (num - min) / b.
Once all n elements have been distributed, we compare numBuckets - 1 adjacent bucket pairs to find the maximum gap.

Here is the implementation in C# -

        public int MaximumGap(int[] nums)

        {

            if (nums?.Length < 2)

            {

                return 0;

            }

            int min = Enumerable.Min(nums);

            int max = Enumerable.Max(nums);

            int gap = (int)Math.Ceiling(((double)(max - min)) / ((double)nums.Length - 1));

            int[] bucketMax = new int[nums.Length - 1];

            Array.Fill(bucketMax, int.MinValue);

            int[] bucketMin = new int[nums.Length - 1];

            Array.Fill(bucketMin, int.MaxValue);

            for (int i = 0; i < nums.Length; ++i)

            {

                if (nums[i] == min || nums[i] == max)

                {

                    continue;

                }

                int index = (nums[i] - min) / gap;

                bucketMax[index] = Math.Max(bucketMax[index], nums[i]);

                bucketMin[index] = Math.Min(bucketMin[index], nums[i]);

            }

            int maxGap = 0, prevMax = min;

            for (int i = 0; i < nums.Length - 1; ++i)

            {

                if (bucketMax[i] == int.MinValue)

                {

                    continue;

                }

                maxGap = Math.Max(maxGap, bucketMin[i] - prevMax);

                prevMax = bucketMax[i];

            }

            return Math.Max(maxGap, max - prevMax);

        }

Complexity: O(n)