<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 maximumGap(vector<int>& nums) {
        int n = nums.size();
        for (long i=1; i<=1000000000; i*=10) {
            vector<int> output(n);
            countSort(nums, i, output);
            nums = output;
        }
        
        int mx = 0;
        for (int i=1; i<n; ++i) {
            int diff = abs(nums[i] - nums[i-1]);
            mx = max(mx, diff);
        }
        return mx;
    }

    void countSort(vector<int> &arr, long exp, vector<int> &output) {
        cout << "size: " << output.size() << '\n';
        int count[10] = {0}, n = arr.size();
        for (int val : arr) {
            count[(val / exp) % 10]++;
        }

        for (int i=1; i<10; ++i) {
            count[i] += count[i - 1];
        }

        // 23 1 9 2 23 18 17

        // 3 1 9 2 3 8
        // count = [0, 1, 1, 2, 0, 0, 0, 0, 1, 1]
        // count = [0, 1, 2, 4, 4, 4, 4, 4, 5, 6]
        // output = [_, _, 3, 3, 8, _]

        for (int i=n-1; i>=0; --i) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
    }
};
109055