<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:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0

        # Pigeonhole principle! Max-min difference split into n-1 buckets
        high = max(nums)
        low = min(nums)
        diff = high - low
        n = len(nums)

        bin_size = max(1, diff // (len(nums)-1))
        n_bins = diff // bin_size + 1
        bins = [[] for i in range(n_bins)]

        # Place nums into bins
        for elem in nums:
            bin_index = (elem - low) // bin_size
            bins[bin_index].append(elem)
        
        # Guaranteed that max difference is b/w adjacent bins (not inside bins)
        # due to pigeonhole principle
        # Won't cover full high-low difference if max difference is inside bin
        bounds = [(min(b), max(b)) for b in bins if b]
        bound_diffs = [next_min[0] - prev_max[1] for prev_max, next_min in zip(bounds[:-1], bounds[1:])]
        return max(bound_diffs) if bound_diffs else 0



        """Inefficient solutions below"""
        # Radix sort O(n)
        # Just one bucket (array not dict), one sorted array
        # sorted_nums = nums.copy()
        # # buckets = [[]] * 10 # Incorrect, all are copies
        # buckets = [[] for i in range(10)]

        # for digit_place in range(0, 10):
        #     for num in sorted_nums:
        #         num_bin = int((num / (10 ** digit_place)) % 10)
        #         buckets[num_bin].append(num)
            
        #     # Concatenate bucket lists with sum!
        #     sorted_nums = sum(buckets, [])
        #     # Reset buckets!
        #     buckets = [[] for i in range(10)]
        
        # # Iterate through sorted nums
        # max_diff = 0
        # for i in range(1, len(sorted_nums)):
        #     max_diff = max(max_diff, sorted_nums[i] - sorted_nums[i-1])

        # return max_diff

        # O(n log n sorting), track max difference
        # nums.sort()
        # max_diff = 0
        # for i in range(1, len(nums)):
        #     max_diff = max(max_diff, nums[i] - nums[i-1])

        # return max_diff


42051