The O(n) Club: When Buckets and Birds Outsmart Sorting — Maximum Gap Edition

The O(n) Club: When Buckets and Birds Outsmart Sorting — Maximum Gap Edition

⚡ TL;DR

If you want the biggest gap between numbers after sorting—but don’t want to pay the O(n log n) sort tax—just break out the buckets and let some mathematical bird magic (“Pigeonhole Principle”) do the heavy lifting.

// Don’t actually submit this in an interview.
Arrays.sort(nums);
int maxGap = 0;
for(int i = 1; i < nums.length; i++) {
    maxGap = Math.max(maxGap, nums[i] - nums[i-1]);
}

🧠 How Devs Usually Mess This Up

We all know the reflex: Arrays.sort, then a one-pass diff. Classic. Sadly, that O(n log n) handshake gets you booted from O(n) club. Even worse, rookies mis-calculate the gap as current max minus previous max (facepalm), or neglect to skip empty buckets—result: negative gaps, awkward bugs, or a silent callback from your interviewer (“Thanks, but we’re looking for someone less… recursive”).

🔍 What’s Actually Going On

This isn’t just “throw numbers into buckets” — it’s choose bucket sizes carefully so each is wide enough that, mathematically, the largest gap can ONLY happen between buckets. (Seriously, even your high school math teacher would approve! Pigeonhole Principle FTW.) Within a bucket, numbers stack tight—no gappy shenanigans. So you only track the min and max for each bucket, and check gaps from the min of the current bucket versus the max of the previous. Quick, clean, interview-proof.

🛠️ PseudoCode

• Check if the array is a snoozefest (less than 2 numbers, or all numbers identical). Return 0 instantly.
  if (nums.length < 2 || min == max) return 0;
• Find global min and max.
  int min = nums[0], max = nums[0]; for(int n : nums){ min=Math.min(min,n); max=Math.max(max,n); }
• Set bucket size:
  int bucketSize = Math.max(1, (max - min + nums.length - 2) / (nums.length - 1));
  (Don’t let buckets collapse into nothingness!)
• Set bucket count:
  int bucketCount = (max-min)/bucketSize + 1;
• Make min/max arrays for each bucket, fill with Integer.MAX_VALUE/MIN_VALUE to spot empties.
• Chuck each number (except min/max) into a bucket:
  int idx = (num - min) / bucketSize; Update that bucket’s min/max as you go.
• Walk through buckets. For every non-empty, gap = bucketMin - prevBucketMax. Update your answer.
• Finally, check the swing from the last bucket to the global max.

💻 The Code

public int maximumGap(int[] nums) {
    if (nums == null || nums.length < 2) return 0;
    int min = nums[0], max = nums[0];
    for (int n : nums) {
        min = Math.min(min, n);
        max = Math.max(max, n);
    }
    if (min == max) return 0;
    int bucketSize = Math.max(1, (max - min + nums.length - 2) / (nums.length - 1));
    int bucketCount = (max - min) / bucketSize + 1;
     int[] bucketMin = new int[bucketCount];
    int[] bucketMax = new int[bucketCount];
    Arrays.fill(bucketMin, Integer.MAX_VALUE);
    Arrays.fill(bucketMax, Integer.MIN_VALUE);
     for (int n : nums) {
        if (n == min || n == max) continue;
        int idx = (n - min) / bucketSize;
        bucketMin[idx] = Math.min(bucketMin[idx], n);
        bucketMax[idx] = Math.max(bucketMax[idx], n);
    }
     int maxGap = 0, prev = min;
    for (int i = 0; i < bucketCount; i++) {
        if (bucketMin[i] == Integer.MAX_VALUE) continue;
        maxGap = Math.max(maxGap, bucketMin[i] - prev);
        prev = bucketMax[i];
    }
    maxGap = Math.max(maxGap, max - prev);
    return maxGap;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Monotony: All numbers equal? That’s a 0-gap snooze-fest. Don’t let your buckets or brain divide by zero.
• Gap Calculation: Don’t do bucketMax[i] - bucketMax[i-1]. It’s bucketMin[i] - prevBucketMax. Nobody likes negative gaps.
• Buckets Left Empty? Embrace Integer.MAX_VALUE/MIN_VALUE — that’s how you know to skip.
• For the JavaScript crowd: Nope, no built-in bucket sort for you here—this is why you’re learning the math.
• O(n) All the Way: Both time and space rival your WiFi speed (in the good way). Sorting? That’s so last interview.

🧠 Interviewer Brain-Tattoo

“Maximum gaps don’t hide in plain sight—they sneak between buckets. Like the bug you swore was fixed last sprint.”