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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int maximumGap(int* nums, int numsSize) {
9 if (numsSize < 2) return 0;
10 qsort(nums, numsSize, sizeof(int), compare);
11 int maxGap = 0;
12 for (int i = 1; i < numsSize; i++) {
13 int gap = nums[i] - nums[i - 1];
14 if (gap > maxGap) maxGap = gap;
15 }
16 return maxGap;
17}This C solution sorts the input array using the built-in qsort function. After sorting, it iterates over the array to calculate the maximum difference between successive elements.
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#
This C solution calculates the bucket size based on the range of numbers and the number of elements in the array. Elements are then placed into buckets which are used to determine the maximum gap between non-empty buckets.