Log inSign up
hardLeetCodeNot Started

Maximum Gap

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 · Standard Array with Gaps:

Input: nums = [3, 6, 9, 1]
Output: 3
Explanation: Sorted form is [1, 3, 6, 9]. Differences are (3-1)=2, (6-3)=3, (9-6)=3. Maximum difference is 3.

Example 2 · Single Element Array:

Input: nums = [10]
Output: 0
Explanation: Array contains less than 2 elements, so return 0.

Example 3 · Duplicate Elements with Zero Gap:

Input: nums = [1, 1, 1, 1]
Output: 0
Explanation: All elements are equal, maximum gap between successive elements is 0.

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Pigeonhole Principle fundamentals
  • Bucket Sort and Radix Sort mechanisms
  • Range partitioning math

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply the Pigeonhole Principle to eliminate intra-bucket comparisons.
  • Derive bucket size: Math.max(1, (maxVal - minVal) / (n - 1)).
  • Track only min and max per bucket to conserve time and space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Calculate minVal and maxVal.
  • Set bucketSize = max(1, (maxVal - minVal) / (N - 1)).
  • Assign elements to buckets and record [bucketMin, bucketMax] per bucket.
  • Measure gap across adjacent non-empty buckets: current.min - prev.max.

Connected Patterns:

Radix SortBucket Sort (Top K Frequent Elements)Pigeonhole Bounding

1. Comparison Sort (Brute Force)

Intuition

Sort the array in ascending order and scan adjacent elements to find the maximum gap.

Algorithm

  1. 1. If nums.length < 2, return 0.
  2. 2. Sort nums in ascending order.
  3. 3. Loop i from 1 to N-1: - maxGap = max(maxGap, nums[i] - nums[i-1]).
  4. 4. Return maxGap.

All Pairs Intermediate Scan (O(N^3) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
In unsorted data, a pair is adjacent in sorted order if no other element falls strictly between them
Visual state
Values and pointers at this exact step
pointers
S
3
6
9
1
0
↑ v
1
2
3
↑ u
Variables at this step
u
1
v
3
gap
2
maxGap
2
Check / comparison
Pair (1, 3): Scan array to see if any element lies in (1, 3)
Decision / next transition
No element in (1, 3). Pair is adjacent in sorted order! Gap = 3 - 1 = 2. Set maxGap = 2.
Why this step matters

In unsorted data, a pair is adjacent in sorted order if no other element falls strictly between them.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Brute Force Approach: Comparison Sort
7int maximumGap(vector<int>& nums) {
8 if (nums.size() < 2) return 0;
9 sort(nums.begin(), nums.end());
10
11 int maxGap = 0;
12 for (int i = 1; i < nums.size(); i++) {
13 maxGap = max(maxGap, nums[i] - nums[i - 1]);
14 }
15 return maxGap;
16}
17
18int main() {
19 vector<int> nums = {3, 6, 9, 1};
20 int result = maximumGap(nums);
21 cout << "Output: " << result << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting takes O(N log N). The linear difference scan takes O(N).
  • Space complexity: O(1) — In-place sort takes O(1) auxiliary memory.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Radix Sort (Better)

Intuition

Sort in linear time by sorting digits from least to most significant using counting sort.

Algorithm

  1. 1. If nums.length < 2, return 0.
  2. 2. Find maxVal. Set exp = 1.
  3. 3. While maxVal / exp > 0: - Run counting sort based on digit (num / exp) % 10 - exp *= 10.
  4. 4. Traverse sorted array to find max adjacent difference.

Comparison Sort + Adjacent Scan (O(N log N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
After sorting, adjacent elements in the array are guaranteed to be consecutive
Visual state
Values and pointers at this exact step
pointers
S
1
3
6
9
0
↑ sorted
1
2
3
Variables at this step
sorted
[1,3,6,9]
maxGap
0
Check / comparison
Sort array ascending: [1, 3, 6, 9]
Decision / next transition
Sorting transforms the problem into finding max adjacent difference.
Why this step matters

After sorting, adjacent elements in the array are guaranteed to be consecutive.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Better Approach: Radix Sort
7void countSort(vector<int>& nums, int exp) {
8 int n = nums.size();
9 vector<int> output(n);
10 int count[10] = {0};
11
12 for (int i = 0; i < n; i++) {
13 count[(nums[i] / exp) % 10]++;
14 }
15 for (int i = 1; i < 10; i++) {
16 count[i] += count[i - 1];
17 }
18 for (int i = n - 1; i >= 0; i--) {
19 int digit = (nums[i] / exp) % 10;
20 output[count[digit] - 1] = nums[i];
21 count[digit]--;
22 }
23 for (int i = 0; i < n; i++) {
24 nums[i] = output[i];
25 }
26}
27
28int maximumGap(vector<int>& nums) {
29 if (nums.size() < 2) return 0;
30 int maxVal = *max_element(nums.begin(), nums.end());
31
32 for (long long exp = 1; maxVal / exp > 0; exp *= 10) {
33 countSort(nums, exp);
34 }
35
36 int maxGap = 0;
37 for (int i = 1; i < nums.size(); i++) {
38 maxGap = max(maxGap, nums[i] - nums[i - 1]);
39 }
40 return maxGap;
41}
42
43int main() {
44 vector<int> nums = {3, 6, 9, 1};
45 int result = maximumGap(nums);
46 cout << "Output: " << result << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N * D) — D is the number of decimal digits (at most 10 for 32-bit integers). Takes 10 passes of O(N) each.
  • Space complexity: O(N) — Output buffer array requires O(N) auxiliary space.

3. Bucket Sort with Pigeonhole Principle (Optimal)

Intuition

Partition range [min, max] into N-1 buckets; max gap is strictly between adjacent non-empty buckets.

Algorithm

  1. 1. If nums.length < 2, return 0.
  2. 2. Find minVal, maxVal. If minVal == maxVal, return 0.
  3. 3. bucketSize = max(1, (maxVal - minVal) / (N - 1)).
  4. 4. bucketCount = (maxVal - minVal) / bucketSize + 1.
  5. 5. For each x in nums: - idx = (x - minVal) / bucketSize - update bucketMin[idx] and bucketMax[idx].
  6. 6. Traverse non-empty buckets, updating maxGap = max(maxGap, bucketMin[i] - prevMax). - prevMax = bucketMax[i].
  7. 7. Return maxGap.

Bucket Sort / Pigeonhole Principle (O(N) Time, O(N) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
By pigeonhole principle, at least one bucket will be empty or sparse, so max gap cannot be within a bucket
Visual state
Values and pointers at this exact step
pointers
S
1
3
6
9
0
↑ min
1
2
3
↑ max
Variables at this step
min
1
max
9
bucketSize
2
bucketCount
4
Check / comparison
Find min = 1, max = 9. Total range = 9 - 1 = 8. n = 4 elements
Decision / next transition
Bucket size = max(1, floor((9 - 1) / (4 - 1))) = floor(8 / 3) = 2. Create 3 buckets.
Why this step matters

By pigeonhole principle, at least one bucket will be empty or sparse, so max gap cannot be within a bucket.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5using namespace std;
6
7// Optimal Approach: Bucket Sort with Pigeonhole Principle
8int maximumGap(vector<int>& nums) {
9 int n = nums.size();
10 if (n < 2) return 0;
11
12 int minVal = *min_element(nums.begin(), nums.end());
13 int maxVal = *max_element(nums.begin(), nums.end());
14 if (minVal == maxVal) return 0;
15
16 int bucketSize = max(1, (maxVal - minVal) / (n - 1));
17 int bucketCount = (maxVal - minVal) / bucketSize + 1;
18
19 vector<int> minBucket(bucketCount, INT_MAX);
20 vector<int> maxBucket(bucketCount, INT_MIN);
21
22 for (int x : nums) {
23 int idx = (x - minVal) / bucketSize;
24 minBucket[idx] = min(minBucket[idx], x);
25 maxBucket[idx] = max(maxBucket[idx], x);
26 }
27
28 int maxGap = 0;
29 int prevMax = minVal;
30
31 for (int i = 0; i < bucketCount; i++) {
32 if (minBucket[i] == INT_MAX) continue; // Empty bucket
33 maxGap = max(maxGap, minBucket[i] - prevMax);
34 prevMax = maxBucket[i];
35 }
36
37 return maxGap;
38}
39
40int main() {
41 vector<int> nums = {3, 6, 9, 1};
42 int result = maximumGap(nums);
43 cout << "Output: " << result << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass to find min/max, another to fill buckets, and a final pass over buckets (at most N+1 buckets). All steps are strictly O(N).
  • Space complexity: O(N) — Buckets array uses O(N) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Standard SortingO(N log N)O(1) or O(N)Sort the array and compute adjacent differences in one pass.Comparison sort takes O(N log N).
2.Better — Radix SortO(N * d)O(N)Sort numbers digit-by-digit using 10 passes of counting sort.Digit extraction overhead.
3.Optimal — Bucket / Pigeonhole SortOptimalO(N)O(N)Distribute elements into (N-1) buckets and scan bucket boundaries in O(N).None; industry-standard optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Array length < 2: return 0 immediately.
  • All elements identical (minVal == maxVal): bucketSize would be 0 without max(1, ...); handle with early return 0.
  • Uniformly spaced elements: e.g. [1, 2, 3, 4] -> returns 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Maximum Gap?

2.Why is the brute force approach suboptimal for large inputs in Maximum Gap?

3.Which data structure or technique enables the optimal solution for Maximum Gap?

Back to DSA Sheet