Sponsored
Sponsored
The simplest approach to solve this problem is to first sort the array. Once sorted, the maximum gap will be found between consecutive elements. By iterating over the sorted array and computing the difference between each pair of consecutive elements, we can find the maximum difference.
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1) as no additional space is used except for variables.
1using System;
2
3public class Solution {
4 public int MaximumGap(int[] nums) {
5 if (nums.Length < 2) return 0;
6 Array.Sort(nums);
7 int maxGap = 0;
8 for (int i = 1; i < nums.Length; i++) {
9 maxGap = Math.Max(maxGap, nums[i] - nums[i - 1]);
10 }
11 return maxGap;
12 }
13}C#'s Array.Sort is used to sort the numbers. The algorithm then computes the maximum difference between consecutive sorted numbers.
This approach leverages the bucket sort idea to achieve linear time complexity. By calculating the bucket size and distributing array elements across buckets, we attempt to isolate maximum differences across distinct buckets, as adjacent elements within a bucket should have a smaller difference.
Time Complexity: O(n) since the bucket placement and scanning are linear operations.
Space Complexity: O(n) for the two bucket arrays.
1#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
int maximumGap(std::vector<int>& nums) {
if (nums.size() < 2) return 0;
int minVal = *std::min_element(nums.begin(), nums.end());
int maxVal = *std::max_element(nums.begin(), nums.end());
int bucketSize = std::max(1, (maxVal - minVal) / ((int)nums.size() - 1));
int bucketCount = (maxVal - minVal) / bucketSize + 1;
std::vector<int> minBucket(bucketCount, std::numeric_limits<int>::max());
std::vector<int> maxBucket(bucketCount, std::numeric_limits<int>::min());
for (int num : nums) {
int idx = (num - minVal) / bucketSize;
minBucket[idx] = std::min(minBucket[idx], num);
maxBucket[idx] = std::max(maxBucket[idx], num);
}
int maxGap = 0, prev = minVal;
for (size_t i = 0; i < minBucket.size(); ++i) {
if (minBucket[i] == std::numeric_limits<int>::max()) continue;
maxGap = std::max(maxGap, minBucket[i] - prev);
prev = maxBucket[i];
}
return maxGap;
}This C++ solution uses a bucket sort-based approach. Buckets are determined based on the range and distributed among captured minimum and maximum bucket values, enabling the detection of the largest maximum gap across non-empty bucket sequences.