<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:
    int getBucketId(int num, int minNum, int bucketSize){
        int x = ( num - minNum ) / bucketSize;
        cout << " idx get: " << x << " val: " << num << endl;
        return x;
    }

    int maximumGap(vector<int>& nums) {
        int minNum = INT_MAX;
        int maxNum = INT_MIN;
        int n = nums.size();
        int ans = 0;

        if ( n <= 1 ) return 0;


        for(int i = 0 ; i < n; i++){
            minNum = min(minNum , nums[i]);
            maxNum = max(maxNum , nums[i]);
        }

        // int diff = ( (maxNum - minNum) == 0 )? 1:(maxNum - minNum);

        // int maxDiff = (maxNum - minNum);

        // 0......maxDiff
        // b1 b2 b3 b4

        if (maxNum - minNum == 0) return 0;
        
        int bucketSize = ceil(((maxNum - minNum)*1.0) / (n - 1) );

        // find bucket = num/gap -> max*n/(max - min)

        vector<pair<int,int>> buckets( n + 1, {INT_MAX, INT_MIN}); // first -> min val, second -> max val

        for(int i = 0 ; i < n ; i++){
            int num = nums[i];
            int bucketId = getBucketId(num, minNum, bucketSize);

            buckets[bucketId].first = min( buckets[bucketId].first , num );
            buckets[bucketId].second = max( buckets[bucketId].second , num );

            ans = max(ans , buckets[bucketId].second - buckets[bucketId].first);
        }

        int l = 0;
        int r = 0;

        // for(int i = 0 ; i < buckets.size(); i++) {
        //     cout << i << " min: " << buckets[i].first << " max: " << buckets[i].second << endl;
        // }

        while(l < buckets.size() && r < buckets.size()) {
            int prevMax = buckets[l].second;

            if (buckets[r].first == INT_MAX){
                r++;
            }
            else {
                int currMin = buckets[r].first;
                ans = max( ans , currMin - prevMax );
                l = r;
                r++;
            }
        }

        return ans;
    }
};
91940