Circle and Rectangle Overlapping: Closest Point Distance Check

LeetCode 1401, Circle and Rectangle Overlapping, asks whether a circle and an axis-aligned rectangle share any point in common. You are given a circle defined by radius, xCenter, and yCenter, plus a rectangle defined by its bottom-left corner (x1, y1) and top-right corner (x2, y2). Return True if there exists at least one point that belongs to both shapes, False otherwise.

The problem

radius = 1, xCenter = 0, yCenter = 0
x1 = 1, y1 = -1, x2 = 3, y2 = 1
# Output: True (the circle just touches the rectangle at (1, 0))

radius = 1, xCenter = 0, yCenter = 0
x1 = -3, y1 = -3, x2 = -1, y2 = -1
# Output: False (the closest corner is too far)

The key insight is that you do not need to check every point on the rectangle's boundary. Instead, find the single closest point on the rectangle to the circle's center. If that point is within the circle (distance from center is at most the radius), the shapes overlap. If even the closest point is too far, nothing else on the rectangle can be closer.

How do you find the closest point? For an axis-aligned rectangle, you handle each axis independently. If the center's x-coordinate is already between x1 and x2, the closest x is just xCenter itself. If it is to the left of the rectangle, the closest x is x1. If it is to the right, the closest x is x2. This is exactly what clamping does: max(x1, min(xCenter, x2)). Same logic for y.

The solution

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int,
                     x1: int, y1: int, x2: int, y2: int) -> bool:
        closest_x = max(x1, min(xCenter, x2))
        closest_y = max(y1, min(yCenter, y2))
        dx = xCenter - closest_x
        dy = yCenter - closest_y
        return dx * dx + dy * dy <= radius * radius

1. Clamp x. max(x1, min(xCenter, x2)) projects the center onto the rectangle's x-range. If the center is inside the range, it stays put. If it is outside, it snaps to the nearest edge.
2. Clamp y. Same operation for the y-axis.
3. Squared distance. Compute dx * dx + dy * dy between the center and the closest point. Using squared distance avoids a square root, which is both faster and avoids floating-point issues.
4. Compare. If the squared distance is at most radius * radius, the closest point on the rectangle is inside (or on the boundary of) the circle, so they overlap.

Step-by-step walkthrough

The first example shows a case where the circle just barely touches the rectangle. The closest point lands exactly on the circle's boundary, so the squared distance equals radius * radius and we return True. The second example pushes the rectangle farther away so the closest point falls outside the circle.

Complexity analysis

This is optimal. You cannot determine overlap without examining at least the center, radius, and rectangle coordinates, and this solution does exactly that.

Building blocks

Clamping to find the nearest point

The core technique here is clamping each coordinate of the circle's center to the rectangle's bounds. This works because an axis-aligned rectangle is a Cartesian product of two intervals. Finding the nearest point on it decomposes into two independent 1D nearest-point problems.

For a single axis, the nearest point on the interval [lo, hi] to a value v is max(lo, min(v, hi)). If v is inside the interval, the nearest point is v itself. If v is outside, the nearest point is whichever endpoint is closer. This clamping pattern appears in collision detection, bounding box checks, and many computational geometry algorithms.

Squared distance comparison

Comparing dx*dx + dy*dy against radius*radius avoids computing a square root. Since both sides are non-negative and squaring preserves the ordering of non-negative numbers, this is mathematically equivalent to checking whether sqrt(dx*dx + dy*dy) is at most radius. Avoiding the square root keeps the solution in pure integer arithmetic, eliminating any floating-point precision concerns.

Edge cases

• Center inside the rectangle. If xCenter is between x1 and x2, and yCenter is between y1 and y2, the closest point is the center itself. The distance is zero, which is always at most radius. The function correctly returns True.
• Circle touching the rectangle at exactly one point. This happens when the squared distance exactly equals radius * radius. The problem says "there exists a point that belongs to both," so touching counts as overlap. The <= comparison handles this correctly.
• Circle far from the rectangle. Both dx and dy are large, the squared distance exceeds radius * radius, and the function returns False.
• Rectangle is a single point. If x1 == x2 and y1 == y2, the rectangle degenerates to a point. Clamping still works correctly, the closest point is that single point, and you just check whether it falls within the circle.
• Very large radius. If the radius is large enough, any finite rectangle will be inside the circle. The clamped distance will be small relative to radius * radius, and the function returns True.

From understanding to recall

The algorithm is short, just five lines, but under interview pressure it is easy to second-guess which direction the clamping should go or whether to use < vs <=. The mental model to lock in is: "clamp, then distance." Clamp the center to the rectangle to find the nearest point, then check if that point is within the circle. Once you can visualize this, the code writes itself.

Practicing this once or twice with spaced repetition ensures you can reproduce the solution from the mental model alone, without needing to re-derive the clamping logic.

Related posts

• Rectangle Overlap checks whether two axis-aligned rectangles overlap using axis projection, a closely related geometric test
• Rectangle Area computes the union area of two rectangles using inclusion-exclusion and interval clamping
• Minimum Area Rectangle finds the smallest rectangle formed by a set of points, exercising similar coordinate geometry reasoning

The clamping technique you learned here is one of the most reusable ideas in computational geometry. Any time you need the closest point on an axis-aligned shape, clamp each coordinate independently.