<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:
    # radix sort, O(k*n)
    # source: https://leetcode.com/problems/maximum-gap/submissions/1093657087
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        elif n == 2:
            # return max(nums[1], nums[0]) - min(nums[1], nums[0])
            return abs(nums[1] - nums[0])
        # bit count for comparison
        BASE = 16
        BUCKET_COUNT = 1 << BASE
        MAX_BITS = 32
        buckets = [0] * BUCKET_COUNT
        prev, cur = nums[:], [0] * n
        for i in range(0, MAX_BITS, BASE):
            mask = (1 << BASE) - 1
            # print(f"block idx: [{i}/{MAX_BITS // BASE - 1}], mask: {bin(mask)}")
            for num in prev:
                # tmp = num >> (BUCKET_COUNT - 1)
                # bucket_idx = tmp & mask
                bucket_idx = (num >> i) & (BUCKET_COUNT - 1)
                # print(f"num: {num}, tmp: {tmp}, bucket_idx = {bin(num)} & {bin(mask)}: {bucket_idx} ({bin(bucket_idx)})")
                buckets[bucket_idx] += 1
            # print(f"sorted buckets: {buckets}")
            for j in range(1, BUCKET_COUNT):
                buckets[j] += buckets[j - 1]
            # print(f"prefixed buckets: {buckets}")
            for num in reversed(prev):
                # tmp = num >> (BUCKET_COUNT - 1)
                # bucket_idx = tmp & mask
                bucket_idx = (num >> i) & (BUCKET_COUNT - 1)
                # print(f"pop num {num} from bucket_idx: {bucket_idx}, buckets[{bucket_idx}]: {buckets[bucket_idx]} -> {buckets[bucket_idx] - 1}")
                buckets[bucket_idx] -= 1
                num_idx = buckets[bucket_idx]
                cur[num_idx] = num
            # print(f"block idx: [{i}/{MAX_BITS // BASE - 1}], cur: {cur}")
            prev, cur = cur, prev
            buckets = [0] * BUCKET_COUNT
        # print(f"sorted: {prev}")
        max_gap = 0
        for i in range(1, n):
            max_gap = max(max_gap, prev[i] - prev[i - 1])
        return max_gap

    # O(n) MLE
    # def maximumGap(self, nums: List[int]) -> int:
    #     n = len(nums)
    #     max_val = max(nums)
    #     present = [False] * (max_val + 1)
    #     for num in nums:
    #         present[num] = True
    #     max_gap = 0
    #     prev = None
    #     for i, isPresent in enumerate(present):
    #         if not isPresent:
    #             continue
    #         if prev is None:
    #             prev = i
    #             continue
    #         max_gap = max(max_gap, i - prev)
    #         prev = i
    #     return max_gap
        
29186