Gap Algorithm (Comparing Elements with Distance)

The gap algorithm (distance / separation thinking) compares elements by how far apart they are—classic pattern: sort, then scan adjacent pairs for minimum gap, or use two pointers when the array is already ordered.

Why this shows up in the real world

GIS mapping, game collision, and competitive programming geometry problems all boil down to coordinates, ordering, and careful integer arithmetic.

Core idea (explained for students)

After sorting by coordinate or value, the answer often lives in adjacent items in that order (e.g. closest pair in 1D). For “max minimum gap”, binary search the gap and check feasibility with greedy placement.

Try this in Python

def min_gap_sorted(nums: list[int]) -> int:
    nums = sorted(nums)
    if len(nums) < 2:
        return 0
    return min(nums[i + 1] - nums[i] for i in range(len(nums) - 1))


print(min_gap_sorted([8, 1, 5, 3, 9]))

Common mistakes

• Checking all O(n²) pairs when sort + linear scan suffices for 1D closest pair.
• Confusing minimum gap with maximum gap problem types.
• Not handling duplicate coordinates (gap can be 0).

Key takeaways

• Sort first; prove why only neighbors matter on a line.
• On a circle, duplicate array and sort or use specialized geometry.