Maximum Gap - Practice Coding Problems

Maximum Gap - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,6,9,1]

› Output: 3

💡 Note: Sorted array is [1,3,6,9]. Gaps are: 3-1=2, 6-3=3, 9-6=3. Maximum gap is 3.

Example 2 — Larger Gap at End

$ Input: nums = [10]

› Output: 0

💡 Note: Array has less than 2 elements, so return 0.

Example 3 — Multiple Large Gaps

$ Input: nums = [1,10000000]

› Output: 9999999

💡 Note: Only two elements, so maximum gap is 10000000 - 1 = 9999999.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Unsorted integer array

Sort

Arrange elements in ascending order

Find Gap

Calculate maximum difference between consecutive elements

Key Takeaway

🎯 Key Insight: Use bucket sort to achieve O(n) time - the maximum gap occurs between buckets, not within them

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that the maximum gap must be at least (max-min)/(n-1), so we can use bucket sort to achieve linear time. The optimal approach uses buckets where the maximum gap occurs between buckets, not within them. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Compare	O(n log n)	O(1)	Sort the array and find maximum difference between consecutive elements
Bucket Sort Approach	O(n)	O(n)	Use buckets to achieve linear time by skipping unnecessary comparisons

Sort and Compare — Algorithm Steps

Sort the array using built-in sort
Iterate through consecutive pairs
Track maximum difference

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort elements in ascending order

Compare Pairs

Check difference between each consecutive pair

Track Maximum

Keep track of the largest gap found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize) {
    if (numsSize < 2) return 0;
    
    qsort(nums, numsSize, sizeof(int), compare);
    int maxGap = 0;
    
    for (int i = 1; i < numsSize; i++) {
        int gap = nums[i] - nums[i-1];
        if (gap > maxGap) {
            maxGap = gap;
        }
    }
    
    return maxGap;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n) time, iteration takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Compare — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler