LeetCode 1401 - Circle and Rectangle Overlapping

LeetCode Problem 1401

Difficulty: 🟡 Medium
Topics: Math, Geometry

Solution

Problem Understanding

The problem gives two geometric shapes:

1. A circle, defined by:

• radius
• center coordinates (xCenter, yCenter)

2. An axis-aligned rectangle, defined by:

• bottom-left corner (x1, y1)
• top-right corner (x2, y2)

The goal is to determine whether the circle and rectangle overlap. Two shapes overlap if there exists at least one point that belongs to both shapes simultaneously.

The rectangle is axis-aligned, which means its edges are parallel to the x-axis and y-axis. This simplifies the geometry significantly because the rectangle boundaries are easy to compare against coordinates.

The important detail is that touching counts as overlapping. If the circle only touches the rectangle at one edge or one corner, the answer is still true.

The constraints are relatively small numerically, but the coordinate range spans negative and positive values. The maximum radius is 2000, and coordinates can go up to 10^4 in magnitude. These constraints suggest that a constant-time geometric solution is expected.

A naive implementation might incorrectly handle several edge cases:

• The circle center may already lie inside the rectangle.
• The circle may touch exactly at a rectangle corner.
• The circle may touch exactly along an edge.
• The rectangle may lie completely inside the circle.
• Coordinates may be negative.
• Distance calculations using square roots can introduce floating point precision issues.

The problem guarantees:

• x1 < x2
• y1 < y2

So the rectangle is always valid and non-degenerate.

Approaches

Brute Force Approach

A brute force idea would be to examine points across the rectangle and check whether any point lies inside the circle. For each sampled point (x, y):

• Compute the squared distance to the circle center:

$$(x - xCenter)^2 + (y - yCenter)^2$$

• If the value is less than or equal to radius^2, then the point lies inside the circle.

This approach is conceptually correct because overlap exists if any shared point exists.

However, the problem is continuous geometry, not discrete geometry. The rectangle contains infinitely many points. A brute force grid scan only works if coordinates are discretized, and even then it becomes inefficient and potentially inaccurate.

For example, iterating over every integer coordinate inside the rectangle could still miss overlaps occurring between integer points.

Optimal Geometric Observation

The key insight is this:

To determine whether the circle overlaps the rectangle, we only need to find the point inside the rectangle that is closest to the circle center.

If the closest point in the rectangle is within the circle, then overlap exists.

If even the closest point is outside the circle, then no overlap exists.

For an axis-aligned rectangle, the closest point can be computed independently for the x-coordinate and y-coordinate using clamping:

• If the center's x-coordinate lies left of the rectangle, use x1
• If it lies right of the rectangle, use x2
• Otherwise use xCenter itself

The same logic applies for the y-coordinate.

This gives the nearest rectangle point (closestX, closestY).

Then compute the squared distance from the circle center to this point. If:

$$(closestX - xCenter)^2 + (closestY - yCenter)^2 \le radius^2$$

then the shapes overlap.

This avoids floating point operations entirely and runs in constant time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(W × H)	O(1)	Scans points inside the rectangle, inefficient and unreliable for continuous geometry
Optimal	O(1)	O(1)	Uses closest-point geometry and squared distance comparison

Algorithm Walkthrough

1. Start with the circle center (xCenter, yCenter) and rectangle boundaries.
2. Find the closest x-coordinate inside the rectangle.

• If xCenter < x1, the closest x-value is x1
• If xCenter > x2, the closest x-value is x2
• Otherwise the center already lies horizontally inside the rectangle, so use xCenter

3. Find the closest y-coordinate inside the rectangle using the same logic.

• If yCenter < y1, use y1
• If yCenter > y2, use y2
• Otherwise use yCenter

4. The resulting point (closestX, closestY) is guaranteed to be the nearest point inside the rectangle to the circle center.
5. Compute the squared Euclidean distance:

$$dx = closestX - xCenter$$

$$dy = closestY - yCenter$$

$$distanceSquared = dx^2 + dy^2$$ 6. Compare this distance against the squared radius:

$$radius^2$$ 7. If distanceSquared <= radius^2, the circle reaches the rectangle, so return true. 8. Otherwise return false.

Why it works

The algorithm works because the nearest point inside a rectangle minimizes Euclidean distance to the circle center. If the minimum possible distance from the center to the rectangle is less than or equal to the radius, then at least one rectangle point lies inside the circle.

Conversely, if even the closest rectangle point is farther than the radius, every other rectangle point must also be farther away, so overlap is impossible.

Python 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 = closest_x - xCenter
        dy = closest_y - yCenter
        
        return dx * dx + dy * dy <= radius * radius

The implementation follows the geometric observation directly.

The first two lines compute the nearest rectangle point to the circle center. The expression:

max(x1, min(xCenter, x2))

effectively clamps xCenter into the rectangle's horizontal range.

If xCenter is smaller than x1, the result becomes x1.

If xCenter is larger than x2, the result becomes x2.

Otherwise it remains unchanged.

The same logic applies to closest_y.

Next, the code computes horizontal and vertical offsets from the center to the closest point.

Finally, instead of computing an actual Euclidean distance using square roots, the implementation compares squared values. This avoids unnecessary floating point operations and is mathematically equivalent.

Go Solution

func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
    
    closestX := max(x1, min(xCenter, x2))
    closestY := max(y1, min(yCenter, y2))
    
    dx := closestX - xCenter
    dy := closestY - yCenter
    
    return dx*dx+dy*dy <= radius*radius
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go implementation mirrors the Python logic closely.

Since Go does not provide built-in integer min and max functions for all versions, helper functions are defined manually.

All calculations remain integer-based, so there are no floating point precision concerns. Integer overflow is also not an issue because the coordinate bounds are small enough for standard Go integers.

Worked Examples

Example 1

radius = 1
center = (0, 0)

rectangle:
x1 = 1, y1 = -1
x2 = 3, y2 = 1

The rectangle spans horizontally from 1 to 3.

The circle center's x-coordinate is 0, which lies left of the rectangle.

So:

Variable	Value
closestX	1
closestY	0

Distance computation:

Expression	Value
dx	1 - 0 = 1
dy	0 - 0 = 0
dx² + dy²	1

Radius squared:

Expression	Value
radius²	1

Since:

$$1 \le 1$$

the answer is true.

The circle touches the rectangle exactly at (1, 0).

Example 2

radius = 1
center = (1, 1)

rectangle:
x1 = 1, y1 = -3
x2 = 2, y2 = -1

Closest rectangle point:

Variable	Value
closestX	1
closestY	-1

Distance computation:

Expression	Value
dx	1 - 1 = 0
dy	-1 - 1 = -2
dx² + dy²	4

Radius squared:

Expression	Value
radius²	1

Since:

$$4 > 1$$

the circle does not reach the rectangle.

Answer: false.

Example 3

radius = 1
center = (0, 0)

rectangle:
x1 = -1, y1 = 0
x2 = 0, y2 = 1

The center already lies on the rectangle boundary.

Closest point:

Variable	Value
closestX	0
closestY	0

Distance computation:

Expression	Value
dx	0
dy	0
distanceSquared	0

Since:

$$0 \le 1$$

the answer is true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a fixed number of arithmetic and comparison operations are performed
Space	O(1)	No extra data structures are allocated

The algorithm performs a constant amount of work regardless of input size. No loops, recursion, or auxiliary storage are used, so both time and space complexities remain constant.

Test Cases

sol = Solution()

# Provided examples
assert sol.checkOverlap(1, 0, 0, 1, -1, 3, 1) is True   # Touching edge
assert sol.checkOverlap(1, 1, 1, 1, -3, 2, -1) is False # Clearly separated
assert sol.checkOverlap(1, 0, 0, -1, 0, 0, 1) is True   # Center on boundary

# Circle center inside rectangle
assert sol.checkOverlap(2, 0, 0, -1, -1, 1, 1) is True  # Rectangle contains center

# Rectangle completely inside circle
assert sol.checkOverlap(10, 0, 0, -1, -1, 1, 1) is True # Circle surrounds rectangle

# Touching exactly at a corner
assert sol.checkOverlap(5, 0, 0, 3, 4, 6, 8) is True    # Distance exactly 5

# Corner just outside circle
assert sol.checkOverlap(4, 0, 0, 3, 4, 6, 8) is False   # Distance exceeds radius

# Circle completely outside horizontally
assert sol.checkOverlap(1, -5, 0, 0, -1, 2, 1) is False

# Circle completely outside vertically
assert sol.checkOverlap(1, 0, 5, -1, -1, 1, 1) is False

# Negative coordinates
assert sol.checkOverlap(3, -5, -5, -8, -8, -4, -4) is True

# Very small overlap
assert sol.checkOverlap(1, 2, 2, 3, 2, 5, 4) is True

# Exact tangency on vertical edge
assert sol.checkOverlap(2, 0, 0, 2, -5, 4, 5) is True

# Exact tangency on horizontal edge
assert sol.checkOverlap(2, 0, 0, -5, 2, 5, 4) is True

Test	Why
Example 1	Validates edge touching
Example 2	Validates separated shapes
Example 3	Validates overlap on boundary
Center inside rectangle	Ensures clamping handles internal points
Rectangle inside circle	Ensures large-radius behavior
Corner tangency	Validates exact distance equality
Corner outside	Ensures strict non-overlap
Outside horizontally	Tests horizontal separation
Outside vertically	Tests vertical separation
Negative coordinates	Confirms coordinate sign handling
Small overlap	Tests minimal valid intersection
Vertical tangency	Ensures edge touching counts
Horizontal tangency	Ensures another tangency scenario

Edge Cases

Circle Center Inside the Rectangle

One important case occurs when the circle center already lies inside the rectangle. In this situation, the closest rectangle point to the center is the center itself.

A buggy implementation might incorrectly search only edges or corners and miss this case entirely.

The clamping logic naturally handles this correctly because both coordinates remain unchanged. The computed distance becomes zero, which always satisfies the overlap condition.

Circle Touching Exactly at a Corner

Another subtle case occurs when the circle only touches one rectangle corner.

For example:

Circle center = (0,0)
Radius = 5
Rectangle corner = (3,4)

The distance equals exactly 5.

Implementations using floating point arithmetic may introduce precision issues and accidentally reject equality cases.

This implementation avoids that by comparing squared integers directly:

$$3^2 + 4^2 = 25$$

$$5^2 = 25$$

Since equality is allowed, overlap is correctly detected.

Circle Completely Outside Along One Axis

A common bug occurs when the circle is horizontally or vertically separated from the rectangle.

For example:

Circle center = (-10, 0)
Rectangle x-range = [0, 5]

The closest x-coordinate must become 0.

The clamping operation handles this precisely. Instead of checking every edge manually, the algorithm directly computes the nearest valid rectangle coordinate.

This guarantees correct behavior for all outside positions, including diagonal separation cases.