Description
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.
Examples:
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.Solution in Python
To solve the problem of finding the maximum difference between two successive elements in the sorted form of an array in linear time using linear extra space, we can use the “bucket sort” or “pigeonhole sort” approach.
Explanation
- Edge Case:
- If the array has less than two elements, return 0.
- Bucket Concept:
- Determine the minimum and maximum values in the array.
- Calculate the bucket size and the number of buckets.
- Distribute the elements into these buckets such that the difference between the maximum and minimum values of each bucket is minimized.
- Bucket Distribution:
- Each bucket will hold a range of values. Place each element in its corresponding bucket.
- Track the minimum and maximum values in each bucket.
- Calculate Maximum Gap:
- After distributing the elements into buckets, calculate the maximum gap by comparing the minimum value of the current bucket with the maximum value of the previous bucket.
Python
from typing import List
class Solution:
def maximumGap(self, nums: List[int]) -> int:
# Edge case: if the array has less than 2 elements, return 0
if len(nums) < 2:
return 0
# Find the minimum and maximum values in the array
min_num, max_num = min(nums), max(nums)
# Calculate the bucket size and the number of buckets
bucket_size = max(1, (max_num - min_num) // (len(nums) - 1))
bucket_count = (max_num - min_num) // bucket_size + 1
# Initialize buckets
buckets = [{'min': float('inf'), 'max': float('-inf')} for _ in range(bucket_count)]
# Distribute the elements into the buckets
for num in nums:
idx = (num - min_num) // bucket_size
buckets[idx]['min'] = min(buckets[idx]['min'], num)
buckets[idx]['max'] = max(buckets[idx]['max'], num)
# Calculate the maximum gap
max_gap = 0
prev_max = min_num
for bucket in buckets:
if bucket['min'] == float('inf'):
# Skip empty buckets
continue
# Update the maximum gap
max_gap = max(max_gap, bucket['min'] - prev_max)
prev_max = bucket['max']
return max_gapDetailed Comments:
- Edge Case:
- If the length of the array is less than 2, return 0 immediately.
- Bucket Initialization:
min_num, max_num = min(nums), max(nums): Find the minimum and maximum values in the array.bucket_size = max(1, (max_num - min_num) // (len(nums) - 1)): Calculate the size of each bucket. Ensure the bucket size is at least 1.bucket_count = (max_num - min_num) // bucket_size + 1: Calculate the number of buckets needed.
- Bucket Distribution:
- Initialize
bucketsas a list of dictionaries to keep track of the minimum and maximum values in each bucket. - For each number in
nums, determine its bucket index and update the minimum and maximum values of the corresponding bucket.
- Initialize
- Calculate Maximum Gap:
- Iterate through the buckets to find the maximum gap. Skip empty buckets.
- The maximum gap is the difference between the minimum value of the current bucket and the maximum value of the previous bucket.
Solution in Javascript
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var maximumGap = function(nums) {
// Edge case: if the array has less than 2 elements, return 0
if (nums.length < 2) {
return 0;
}
// Find the minimum and maximum values in the array
let minNum = Math.min(...nums);
let maxNum = Math.max(...nums);
// Calculate the bucket size and the number of buckets
let bucketSize = Math.max(1, Math.floor((maxNum - minNum) / (nums.length - 1)));
let bucketCount = Math.floor((maxNum - minNum) / bucketSize) + 1;
// Initialize buckets
let buckets = new Array(bucketCount).fill(null).map(() => ({
min: Infinity,
max: -Infinity
}));
// Distribute the elements into the buckets
for (let num of nums) {
let idx = Math.floor((num - minNum) / bucketSize);
buckets[idx].min = Math.min(buckets[idx].min, num);
buckets[idx].max = Math.max(buckets[idx].max, num);
}
// Calculate the maximum gap
let maxGap = 0;
let prevMax = minNum;
for (let bucket of buckets) {
if (bucket.min === Infinity) {
// Skip empty buckets
continue;
}
// Update the maximum gap
maxGap = Math.max(maxGap, bucket.min - prevMax);
prevMax = bucket.max;
}
return maxGap;
};Solution in Java
Java
class Solution {
public int maximumGap(int[] nums) {
// Edge case: if the array has less than 2 elements, return 0
if (nums.length < 2) {
return 0;
}
// Find the minimum and maximum values in the array
int minNum = Integer.MAX_VALUE;
int maxNum = Integer.MIN_VALUE;
for (int num : nums) {
minNum = Math.min(minNum, num);
maxNum = Math.max(maxNum, num);
}
// Calculate the bucket size and the number of buckets
int bucketSize = Math.max(1, (maxNum - minNum) / (nums.length - 1));
int bucketCount = (maxNum - minNum) / bucketSize + 1;
// Initialize buckets
int[][] buckets = new int[bucketCount][2];
for (int i = 0; i < bucketCount; i++) {
buckets[i][0] = Integer.MAX_VALUE; // min value in the bucket
buckets[i][1] = Integer.MIN_VALUE; // max value in the bucket
}
// Distribute the elements into the buckets
for (int num : nums) {
int idx = (num - minNum) / bucketSize;
buckets[idx][0] = Math.min(buckets[idx][0], num);
buckets[idx][1] = Math.max(buckets[idx][1], num);
}
// Calculate the maximum gap
int maxGap = 0;
int prevMax = minNum;
for (int[] bucket : buckets) {
if (bucket[0] == Integer.MAX_VALUE) {
// Skip empty buckets
continue;
}
// Update the maximum gap
maxGap = Math.max(maxGap, bucket[0] - prevMax);
prevMax = bucket[1];
}
return maxGap;
}
}Solution in C#
C#
public class Solution {
public int MaximumGap(int[] nums) {
// Edge case: if the array has less than 2 elements, return 0
if (nums.Length < 2) {
return 0;
}
// Find the minimum and maximum values in the array
int minNum = int.MaxValue;
int maxNum = int.MinValue;
foreach (int num in nums) {
minNum = Math.Min(minNum, num);
maxNum = Math.Max(maxNum, num);
}
// Calculate the bucket size and the number of buckets
int bucketSize = Math.Max(1, (maxNum - minNum) / (nums.Length - 1));
int bucketCount = (maxNum - minNum) / bucketSize + 1;
// Initialize buckets
int[][] buckets = new int[bucketCount][];
for (int i = 0; i < bucketCount; i++) {
buckets[i] = new int[] { int.MaxValue, int.MinValue };
}
// Distribute the elements into the buckets
foreach (int num in nums) {
int idx = (num - minNum) / bucketSize;
buckets[idx][0] = Math.Min(buckets[idx][0], num); // Update min value in the bucket
buckets[idx][1] = Math.Max(buckets[idx][1], num); // Update max value in the bucket
}
// Calculate the maximum gap
int maxGap = 0;
int prevMax = minNum;
foreach (int[] bucket in buckets) {
if (bucket[0] == int.MaxValue) {
// Skip empty buckets
continue;
}
// Update the maximum gap
maxGap = Math.Max(maxGap, bucket[0] - prevMax);
prevMax = bucket[1];
}
return maxGap;
}
}