Is Maximum Gap easy or hard?

Maximum Gap is generally considered a medium-level problem. The sorting solution is easy to implement, but recognizing the linear-time bucket strategy requires deeper understanding of distribution-based sorting and gap analysis.

Maximum Gap Python/Java solution

In Python or Java, the straightforward implementation sorts the array and scans adjacent elements to compute the largest difference. The optimized version creates bucket arrays for minimum and maximum values and performs linear scans to determine the maximum inter-bucket gap.

How to solve Maximum Gap in O(n)?

Compute the global minimum and maximum values, then determine the bucket size using (max - min) / (n - 1). Create buckets that store only the minimum and maximum values for each range. After distributing numbers into buckets, scan across buckets and compute gaps between consecutive non-empty buckets to find the maximum.

What is the best approach for Maximum Gap?

The optimal approach uses bucket sort based on the pigeonhole principle. Instead of sorting all elements, it distributes numbers into buckets using the expected minimum gap size. The maximum difference is then computed between the maximum of one bucket and the minimum of the next non-empty bucket. This achieves O(n) time and O(n) space.

Is Maximum Gap asked at Google/Amazon/Meta?

Maximum Gap appears in interview preparation lists for companies like Amazon, Google, and other large tech firms because it tests understanding of bucket-based sorting and the pigeonhole principle. It is commonly used to evaluate whether candidates can move beyond standard comparison sorting.

What data structure is used in Maximum Gap?

The optimal solution uses an array of buckets where each bucket stores two values: a minimum and maximum element. This structure allows the algorithm to track boundary values efficiently without storing every element in sorted order.

What is the time complexity of Maximum Gap?

The simplest solution sorts the array and scans for the largest adjacent difference, which takes O(n log n) time. The optimal bucket-based approach runs in O(n) time because it performs a few linear passes over the array and bucket list.

Description Solution Video 14:54

164. Maximum Gap

Medium53.4% acceptance7 companies

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:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

Asked at 7 companies

Waymo

Google Amazon Microsoft Meta

TCS Bloomberg

Topics

14:54

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

164. Maximum Gap

Asked at 7 companies

Topics

Similar problems