Maximum Gap (Pigeonhole / Sort + Scan)

📋

Problem

Imagine you have a list of timestamps when events occurred, and you want to find the longest idle time between any two consecutive events.

Given an unsorted array of integers nums, return the maximum difference between the successive elements in its sorted form. If the array contains less than two elements, return 0.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^9

Edge cases: Array with one element → output 0Array with all elements equal → output 0Array with two elements → output difference between them

</>

IDE

def maximumGap(nums: List[int]) -> int:public int maximumGap(int[] nums)int maximumGap(vector<int>& nums)function maximumGap(nums)

def maximumGap(nums: List[int]) -> int:
    # Write your solution here
    pass

class Solution {
    public int maximumGap(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maximumGap(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function maximumGap(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for all inputs without sorting or scanning.✅ Add sorting and scan adjacent pairs to compute max gap.

Wrong: max element - min elementReturning difference between max and min without checking adjacent gaps.✅ Sort array and find maximum difference between consecutive elements, not just extremes.

Wrong: Incorrect gap due to off-by-one indexingLoop iterates incorrectly, missing last pair or starting at wrong index.✅ Loop from i=1 to len(nums)-1 and compute nums[i] - nums[i-1].

Wrong: TLE or timeoutUsing O(n^2) brute force approach checking all pairs.✅ Use sorting (O(n log n)) and single pass scan (O(n)) to find max gap.

✓

Test Cases

Focus on handling minimal and uniform inputs correctly.

Consider tricky inputs that break naive or greedy logic.

Optimize your solution to handle large inputs efficiently.

t1_01basic

Input[3,6,9,1]

Expected3

⏱ Performance - must finish in 2000ms

Sorted array is [1,3,6,9], maximum gap is max(3-1=2,6-3=3,9-6=3) = 3

💡 Sort the array first to compare adjacent elements easily.

💡 Check the differences between consecutive sorted elements to find the max gap.

💡 Return the maximum difference found between any two adjacent elements after sorting.

Why it failed: Output incorrect - likely forgot to sort or computed gaps incorrectly. Fix by sorting nums before scanning adjacent differences.

✓ Correctly sorts and finds maximum adjacent gap.

t1_02basic

Input[10,1,5,8]

Expected5

⏱ Performance - must finish in 2000ms

Sorted array is [1,5,8,10], max gaps are 4,3,2; maximum gap is 5-1=4, 8-5=3, 10-8=2; max is 4

💡 Sort the array and then scan adjacent pairs for differences.

💡 Remember to handle all pairs, not just first or last.

💡 Return the largest difference found between consecutive elements.

Why it failed: Incorrect max gap - possibly off-by-one error in loop or missed last pair. Fix loop to check all adjacent pairs after sorting.

✓ Correctly computes max gap by scanning all adjacent pairs.

t2_01edge

Input[5]

Expected0

⏱ Performance - must finish in 2000ms

Only one element, no adjacent pairs, so max gap is 0.

💡 If array length is less than 2, max gap is zero by definition.

💡 Check for length before sorting or scanning.

💡 Return 0 immediately if nums has fewer than two elements.

Why it failed: Fails single element case - likely no length check before processing. Fix by returning 0 if length < 2.

✓ Correctly handles single element input by returning 0.

t2_02edge

Input[7,7,7,7]

Expected0

⏱ Performance - must finish in 2000ms

All elements equal, differences between adjacent elements are zero, max gap is 0.

💡 Sorting equal elements keeps them the same; gaps are zero.

💡 Check that max gap calculation handles zero differences correctly.

💡 Return 0 if all adjacent differences are zero.

Why it failed: Fails equal elements case - possibly returns non-zero or skips zero gaps. Fix by correctly computing max gap including zero differences.

✓ Correctly returns 0 when all elements are equal.

t2_03edge

Input[1,1000000000]

Expected999999999

⏱ Performance - must finish in 2000ms

Two elements with large difference, max gap is difference between them.

💡 Sorting two elements is trivial; max gap is their difference.

💡 Check for integer overflow or type issues with large values.

💡 Return absolute difference between the two elements.

Why it failed: Fails large range two-element case - possibly integer overflow or incorrect difference calculation. Fix by using appropriate data type and correct subtraction.

✓ Correctly computes max gap for large range two-element input.

t3_01corner

Input[1,3,2,7,5]

Expected2

⏱ Performance - must finish in 2000ms

Sorted array is [1,2,3,5,7], gaps are 1,1,2,2; max gap is 2. Tests greedy trap of picking local max gaps incorrectly.

💡 Sorting is essential; do not pick gaps without sorting.

💡 Check all adjacent pairs after sorting, not just local max differences.

💡 Return the maximum gap found after sorting entire array.

Why it failed: Fails greedy trap - likely picks max gap without sorting or only local pairs. Fix by sorting array before scanning all adjacent pairs.

✓ Correctly handles non-monotonic input by sorting first.

t3_02corner

Input[1,1,1,10,10,10]

Expected9

⏱ Performance - must finish in 2000ms

Sorted array is [1,1,1,10,10,10], max gap is 10-1=9 between last 1 and first 10. Tests handling duplicates correctly.

💡 Duplicates do not affect max gap except zero differences.

💡 Check that max gap is computed between distinct values correctly.

💡 Return max gap ignoring zero differences between duplicates.

Why it failed: Fails duplicate handling - possibly returns 0 or incorrect max gap. Fix by scanning all adjacent pairs including duplicates.

✓ Correctly computes max gap with duplicates present.

t3_03corner

Input[100,3,50,1,99]

Expected47

⏱ Performance - must finish in 2000ms

Sorted array is [1,3,50,99,100], gaps are 2,47,49,1; max gap is 49. Tests off-by-one errors in indexing.

💡 Ensure loop iterates from i=1 to n-1 to cover all pairs.

💡 Check indexing carefully to avoid off-by-one errors.

💡 Return max gap after scanning all adjacent pairs correctly.

Why it failed: Fails off-by-one error - likely misses last pair or miscalculates gap. Fix loop bounds to cover all adjacent pairs.

✓ Correctly computes max gap with proper indexing.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000, O(n log n) sorting must complete within 2 seconds.

💡 Use efficient sorting algorithms with O(n log n) complexity.

💡 Avoid nested loops or O(n^2) approaches.

💡 Implement sorting and single pass scan to find max gap.

Why it failed: TLE due to O(n^2) or brute force approach. Fix by using efficient sort and single scan (O(n log n)) solution.

✓ Algorithm runs within time limit using O(n log n) sorting and linear scan.

Practice

1. You are given two integer arrays where the first array needs to be sorted such that the relative order of items in the first array follows the order defined by the second array. Elements not present in the second array should be placed at the end in ascending order. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach by repeatedly selecting the smallest element from the first array that appears in the second array

B. Brute force nested loops checking each element of the first array against the second array

C. Dynamic programming to find the longest subsequence matching the order of the second array

D. Counting sort based on frequency arrays combined with the order defined by the second array

Solution

1. Step 1: Understand problem constraints

   The problem requires sorting the first array so that elements appear in the order defined by the second array, with leftover elements sorted ascending at the end.

2. Step 2: Identify optimal approach

   Counting sort using frequency arrays efficiently counts occurrences and outputs elements in the required order in O(n + k) time, where k is max element value.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Counting sort matches problem constraints and is optimal for integer ranges [OK]

Hint: Frequency counting suits custom order sorting [OK]

Common Mistakes:

• Assuming greedy selection suffices without frequency counting
• Confusing this with subsequence or DP problems
• Using brute force nested loops which is inefficient

2. The following code attempts to find the minimum absolute difference but contains a subtle bug. Which line causes incorrect results?

def minimum_abs_difference(arr):
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        diff = arr[i + 1] - arr[i]
        if diff < min_diff:
            min_diff = diff
    arr.sort()
    return min_diff

medium

A. Line 2: initializing min_diff before sorting

B. Line 6: sorting after scanning pairs

C. Line 7: returning min_diff without recomputing

D. Line 3: iterating without sorting first

Solution

1. Step 1: Identify order of operations

   The array is scanned for differences before sorting, so adjacent pairs are not guaranteed to be closest.

2. Step 2: Pinpoint the bug

   Line 3 iterates over unsorted array, causing incorrect min_diff.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting must happen before scanning adjacent pairs [OK]

Hint: Must sort before scanning adjacent pairs [OK]

Common Mistakes:

• Sorting after scanning
• Not updating min_diff correctly

3. What is the time complexity of the optimal diagonal sorting algorithm that uses a min-heap per diagonal for an m x n matrix, where each diagonal is sorted independently?

medium

A. O(m * n * min(m, n)) because sorting each diagonal requires scanning all elements multiple times.

B. O(m * n * log(m * n)) because all elements are pushed into heaps together.

C. O(m * n) because each element is processed once with constant-time heap operations.

D. O(m * n * log(min(m, n))) because each diagonal has at most min(m, n) elements and heap operations cost log of diagonal length.

Solution

1. Step 1: Identify diagonal lengths

   Each diagonal has at most min(m, n) elements, so heap operations per element cost O(log(min(m, n))).

2. Step 2: Calculate total heap operations

   All m*n elements are pushed and popped once, each operation O(log(min(m, n))). Total time is O(m * n * log(min(m, n))).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap operations dominate and depend on diagonal length, not total elements [OK]

Hint: Heap ops cost log of diagonal length, not total elements [OK]

Common Mistakes:

• Assuming log(m*n) instead of log(min(m,n))
• Ignoring heap operation cost
• Mistaking linear heap ops for constant time

4. Consider the following buggy implementation of wiggle sort. Which line contains the subtle bug that causes the algorithm to fail on inputs with duplicates?

medium

A. Line 9: def virtual_index(i): return (1 + 2 * i) % (n | 1)

B. Line 3: nums.sort()

C. Line 4: median = nums[n // 2]

D. Line 15: elif nums[vi] < median:

Solution

1. Step 1: Identify median calculation

   The median is incorrectly chosen as nums[n // 2], which is the upper median for even-length arrays, but the algorithm requires the lower median nums[(n - 1) // 2].

2. Step 2: Understand impact on partitioning

   Incorrect median causes wrong partitioning of elements equal to median, leading to clustering and violation of wiggle property especially with duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct median index is (n - 1) // 2, not n // 2 [OK]

Hint: Median index off-by-one breaks partitioning with duplicates [OK]

Common Mistakes:

• Using n//2 instead of (n-1)//2 for median
• Ignoring duplicates in partitioning
• Misusing virtual indexing

5. Suppose the problem is modified so that elements in arr1 can appear multiple times and must be reused unlimited times in the output, respecting arr2 order first, then ascending leftover elements. Which modification to the optimal counting sort approach correctly handles this?

hard

A. Keep frequency counts as is and output elements only once per frequency count

B. Modify frequency array to store maximum allowed reuse counts and output elements repeatedly based on that

C. Remove frequency counting and use a hash map to track counts, then output elements in arr2 order repeated as needed

D. Ignore frequency counts and output elements in arr2 order repeatedly until a fixed output size is reached

Solution

1. Step 1: Understand reuse requirement

   Unlimited reuse means frequency counts must represent maximum allowed repeats, not just input counts.

2. Step 2: Modify frequency array accordingly

   Frequency array should store max reuse counts; output elements repeatedly based on these counts respecting arr2 order.

3. Step 3: Reject naive approaches

   Simply outputting once or ignoring counts breaks correctness; hash map alone doesn't handle unlimited reuse without max counts.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Frequency array extended to max reuse counts handles unlimited repeats correctly [OK]

Hint: Unlimited reuse requires frequency counts to represent max repeats [OK]

Common Mistakes:

• Outputting elements only once ignoring reuse
• Using hash map without max reuse logic
• Repeating output arbitrarily without frequency control