Maximum Gap
<p>Given an integer array <code>nums</code>, return <em>the maximum difference between two successive elements in its sorted form</em>. If the array contains less than two elements, return <code>0</code>.</p>

<p>You must write an algorithm that runs in linear time and uses linear extra space.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,6,9,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [10]
<strong>Output:</strong> 0
<strong>Explanation:</strong> The array contains less than 2 elements, therefore return 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>
Array; Bucket Sort; Radix Sort; Sorting
using System;
using System.Linq;

public class Solution {
    public int MaximumGap(int[] nums) {
        if (nums.Length < 2) return 0;
        var max = nums.Max();
        var min = nums.Min();
        var bucketSize = Math.Max(1, (max - min) / (nums.Length - 1));
        var buckets = new Tuple<int, int>[(max - min) / bucketSize + 1];
        foreach (var num in nums)
        {
            var index = (num - min) / bucketSize;
            if (buckets[index] == null)
            {
                buckets[index] = Tuple.Create(num, num);
            }
            else
            {
                buckets[index] = Tuple.Create(Math.Min(buckets[index].Item1, num), Math.Max(buckets[index].Item2, num));
            }
        }

        var result = 0;
        Tuple<int, int> lastBucket = null;
        for (var i = 0; i < buckets.Length; ++i)
        {
            if (buckets[i] != null)
            {
                if (lastBucket != null)
                {
                    result = Math.Max(result, buckets[i].Item1 - lastBucket.Item2);
                }
                lastBucket = buckets[i];
            }
        }
        return result;
    }
}
