The Maximum Gap problem on LeetCode asks us to find the maximum difference between any two adjacent elements in an unsorted array of integers. The formal statement of the problem is as follows:

Given an unsorted array of integers, find the maximum difference between any two adjacent elements. If there is no adjacent element (i.e., the array is empty or has only one element), return 0.

To solve this problem, we will use an algorithm called Radix Sort. The basic idea behind Radix Sort is to sort the elements of an array based on their digits from least significant to most significant.

Here are the steps for Radix Sort:

Step 1: Find the maximum number in the given array, and count the number of digits it has. Let's call this count "d."

Step 2: For each digit i from 0 to d-1, perform the following steps:

• Create d buckets (i.e., arrays), one for each digit from 0 to 9.
• For each element in the given array, put it in the bucket corresponding to its i-th digit (i.e., the one in the i-th place from the right).
• Concatenate the elements of all the buckets in order, from bucket 0 to bucket 9.
• Update the given array with the concatenated elements.

Step 3: After all the digits have been sorted, loop over the array and compute the maximum difference between adjacent elements. Return this maximum difference.

Let's see this algorithm in action with an example. Suppose we have the following unsorted array of integers:

[170, 45, 75, 90, 802, 24, 2, 66]

Step 1: The maximum number in the array is 802, which has three digits. Therefore, d = 3.

Step 2: Sorting by digits, we get:

• i = 0: Buckets: [2, 802, 24], [45, 75], [], [66], [], [], [], [170], [90]. Concatenated buckets: [2, 802, 24, 45, 75, 66, 170, 90]. Array after update: [2, 802, 24, 45, 75, 66, 170, 90].
• i = 1: Buckets: [2, 24, 45, 66, 170, 90], [], [], [], [], [802], [], [], [], [75]. Concatenated buckets: [2, 24, 45, 66, 170, 90, 802, 75]. Array after update: [2, 24, 45, 66, 170, 90, 802, 75].
• i = 2: Buckets: [2, 24, 45, 66, 75, 90], [], [], [], [], [], [], [], [], [170, 802]. Concatenated buckets: [2, 24, 45, 66, 75, 90, 170, 802]. Array after update: [2, 24, 45, 66, 75, 90, 170, 802].

Step 3: The maximum difference between adjacent elements is 632, which occurs between 170 and 802. Therefore, the answer to the problem is 632.

Here's the Python code for the solution:

def maximumGap(nums): if len(nums) < 2: return 0

# Step 1
max_num = max(nums)
d = 0
while max_num > 0:
    max_num //= 10
    d += 1

# Step 2
exp = 1
for i in range(d):
    buckets = [[] for _ in range(10)]
    for num in nums:
        digit = (num // exp) % 10
        buckets[digit].append(num)
    nums = [num for bucket in buckets for num in bucket]
    exp *= 10

# Step 3
max_gap = 0
for i in range(1, len(nums)):
    max_gap = max(max_gap, nums[i] - nums[i-1])
    
return max_gap

Example usage

nums = [170, 45, 75, 90, 802, 24, 2, 66] print(maximumGap(nums)) # Output: 632

1