Maximum Gap

Maximum Gap

What is this problem about?

The Maximum Gap coding problem asks you to find the maximum difference between successive elements in the sorted form of an unsorted array. In other words, once you sort the array, what is the largest gap between any two consecutive numbers? The twist that makes this genuinely interesting is the constraint: you must solve it in O(n) time and O(n) space, which rules out standard comparison-based sorting.

Why is this asked in interviews?

Companies like Microsoft, Google, Meta, and Amazon include Maximum Gap in their interview sets because it probes knowledge of non-comparison-based sorting algorithms. Most candidates default to quick sort or merge sort; this problem forces you to think about bucket sort or radix sort. It also tests whether you understand the pigeonhole principle as a mathematical tool for bounding the answer — a level of reasoning that separates strong candidates from average ones.

Algorithmic pattern used

The standard approach uses bucket sort combined with the pigeonhole principle. Given n elements spanning a range [min, max], the maximum gap must be at least ceil((max - min) / (n - 1)). You create n-1 buckets, each of size at least that minimum gap. For any two elements landing in the same bucket, their difference is smaller than the bucket size, so the maximum gap must span across at least one empty bucket. You only need to track the min and max of each bucket, then scan adjacent non-empty buckets to find the largest gap.

Example explanation

Array: [3, 6, 9, 1]

• Min = 1, Max = 9, n = 4
• Minimum possible max gap = ceil((9-1)/(4-1)) = ceil(2.67) = 3
• Create 3 buckets of size 3: [1,3], [4,6], [7,9]
• Place elements: 3→bucket0, 6→bucket1, 9→bucket2, 1→bucket0
• Bucket 0: min=1, max=3; Bucket 1: min=6, max=6; Bucket 2: min=9, max=9
• Gaps across adjacent buckets: 6-3=3, 9-6=3
• Maximum gap = 3

Common mistakes candidates make

• Using O(n log n) sort: Missing the linear time constraint entirely.
• Incorrect bucket size calculation: Using integer division instead of ceiling leads to wrong bucket boundaries.
• Handling duplicate min/max: If all elements are identical, the gap is 0 — a special case that trips up many implementations.
• Indexing errors with bucket boundaries: Elements exactly at the boundary need to be placed consistently (either inclusive-left or inclusive-right).

Interview preparation tip

For the Array Bucket Sort Sorting Radix Sort interview pattern, memorize the bucket sort template for this problem type. The key insight to communicate in interviews is the pigeonhole principle argument: "If I have n-1 buckets and n elements, at least one bucket must contain two elements, so the max gap cannot come from within a bucket." This explanation demonstrates mathematical maturity and impresses interviewers.