<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>

class Solution {
public:
    vector<int> bucket[1024];
    void radix_sort(vector<int>& nums){
        int x;
        //round 1
        for(int i{};i<nums.size();++i){
            bucket[nums[i]&1023].push_back(nums[i]);
        }
        x=0;
        for(auto &b : bucket){
            copy(b.begin(), b.end(), nums.begin() +x);
            x+=b.size();
            b.clear();
        }
        //round 2
        for(int i{};i<nums.size();++i){
            bucket[(nums[i]>>10)&1023].push_back(nums[i]);
        }
        x=0;
        for(auto &b: bucket){
            copy(b.begin(),b.end(), nums.begin()+x);
            x+=b.size();
            b.clear();
        }
        //round 3
        for(int i{};i<nums.size();++i){
            bucket[nums[i]>>20].push_back(nums[i]);
        }
        x=0;
        for(auto &b: bucket){
            copy(b.begin(), b.end(), nums.begin()+x);
            x+=b.size();
            b.clear();
        }
        //round 4
        // for(int i{};i<nums.size();++i){
        //     bucket[(nums[i]>>21)].push_back(nums[i]);
        // }
        // i=0;
        // for(auto &b: bucket){
        //     copy(b.begin(), b.end(), nums.begin()+i);
        //     i+=b.size();
        //     //b.clear();
        // }
    }
    int maximumGap(vector<int>& nums) {
         radix_sort(nums);
        int ans =0;
        if(nums.size()==1)return 0;
        for(int i{1};i<nums.size();++i)ans=max(ans, nums[i]-nums[i-1]);
        return ans;
    }
};

// auto init=[]{
//     ios_base::sync_with_stdio(0);
//     cin.tie(NULL);cout.tie(NULL);
//     return 0;
// }();
106610