Algorithm
Problem Name: 164. Maximum Gap
Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.
You must write an algorithm that runs in linear time and uses linear extra space.
Example 1:
Input: nums = [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.
Example 2:
Input: nums = [10] Output: 0 Explanation: The array contains less than 2 elements, therefore return 0.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int maximumGap(int num[], int n) {
if (n < 2) return 0;
/* radix sort */
int *sorted_num = (int *)calloc(n, sizeof(int));
int *temp = (int *)calloc(n, sizeof(int));
memcpy(sorted_num, num, sizeof(int) * n);
int i, j;
int shift;
for (shift = 0; shift < 32; shift += 8) {
int count[0x100] = {};
for (i = 0; i < n; i++) {
count[(sorted_num[i] >> shift) & 0xFF] ++;
}
int idx = 0, t = 0;
for (j = 0; j < 0x100; j++) {
t = count[j];
count[j] = idx;
idx += t;
}
for (i = 0; i < n; i++) {
temp[count[(sorted_num[i] >> shift) & 0xFF] ++] = sorted_num[i];
}
int *p = sorted_num;
sorted_num = temp;
temp = p;
}
int max_diff = 0;
for (i = 1; i < n; i++) {
if (sorted_num[i] - sorted_num[i - 1] > max_diff) {
max_diff = sorted_num[i] - sorted_num[i - 1];
}
}
free(sorted_num);
free(temp);
return max_diff;
}
int main() {
int A[] = { 4, 5, 3, 2, 9, 12, 32, 5 };
/* should be 20 = abs(12 - 32) */
printf("%d\n", maximumGap(A, sizeof(A)/sizeof(A[0])));
return 0;
}
Input
nums = [3,6,9,1]
Output
3
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const maximumGap = function (nums) {
if (nums.length < 2) return
let max = 0
nums = nums.sort(function (a, b) {
return a - b
})
for (let i = 1; i < nums.length; i++) {
if (nums[i] - nums[i - 1] > max) max = nums[i] - nums[i - 1]
}
return max
}
Input
nums = [3,6,9,1]
Output
3
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maximumGap(self, nums):
if len(nums) < 2:
return 0
n, mn, mx= len(nums), min(nums), max(nums)
bSize = max(1, (mx - mn) // n + 1)
bNum = (mx - mn) // bSize + 1
buckets = [[float("inf"), -float("inf")] for _ in range(bNum)]
for num in nums:
ind = (num - mn) // bSize
if num < buckets[ind][0]:
buckets[ind][0] = num
if num > buckets[ind][1]:
buckets[ind][1] = num
gap = 0
for i in range(1, bNum):
if buckets[i] == [float("inf"), -float("inf")]:
buckets[i] = buckets[i - 1]
gap = max(gap , buckets[i][0] - buckets[i - 1][1])
return gap
Input
nums = [10]