#1401

Medium

LeetCode Problem Workspace

Circle and Rectangle Overlapping

Determine if a circle intersects with an axis-aligned rectangle using geometric distance checks efficiently in code.

Problem Statement

Given a circle defined by its radius and center coordinates, and an axis-aligned rectangle defined by its bottom-left and top-right corners, determine if the circle and rectangle overlap. Overlap means at least one point lies within both the circle and the rectangle simultaneously. Return true if they overlap, otherwise false.

The circle is represented as (radius, xCenter, yCenter) and the rectangle as (x1, y1, x2, y2). Constraints ensure the circle radius is positive and rectangle coordinates are valid, with x1 < x2 and y1 < y2. Use geometric reasoning to find the closest point on the rectangle to the circle's center and check if the distance is within the circle's radius.

Examples

Example 1

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1

Output: true

Circle and rectangle share the point (1,0).

Example 2

Input: radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1

Output: false

Example details omitted.

Example 3

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1

Output: true

Example details omitted.

Constraints

1 <= radius <= 2000
-104 <= xCenter, yCenter <= 104
-104 <= x1 < x2 <= 104
-104 <= y1 < y2 <= 104

Solution Approach

Clamp Center to Rectangle

Compute the closest point on the rectangle to the circle's center by clamping xCenter between x1 and x2, and yCenter between y1 and y2. This identifies the nearest candidate point for overlap testing.

Distance Evaluation

Calculate the squared distance between the circle's center and the clamped point. If the squared distance is less than or equal to radius squared, the circle and rectangle overlap. This avoids unnecessary square root computations.

Return Boolean Result

Return true if the computed squared distance is within radius squared, false otherwise. This handles all edge cases including corners and sides efficiently using the Math plus Geometry approach.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) because it involves a constant number of arithmetic operations, clamping, and a single distance computation. Space complexity is O(1) since no additional data structures are required.

What Interviewers Usually Probe

Look for edge cases where the circle barely touches rectangle corners.
Check if candidates properly handle clamping for nearest rectangle points.
Confirm avoidance of iterating over all rectangle points for efficiency.

Common Pitfalls or Variants

Common pitfalls

Forgetting to clamp the center coordinates correctly can give false negatives.
Using Euclidean distance without squaring may cause precision issues or unnecessary computation.
Not handling corner touches separately can fail test cases where the circle grazes the rectangle.

Follow-up variants

Rectangle may be rotated; requires rotated rectangle distance checks.
Multiple circles overlapping a single rectangle; sum of squared distances for all centers.
Circle defined by bounding box instead of center/radius; convert to standard circle for overlap check.

FAQ

What is the easiest way to check Circle and Rectangle Overlapping?

Clamp the circle center coordinates to the rectangle bounds and check if the squared distance to this closest point is less than or equal to the radius squared.

Does this approach handle rectangles of all sizes?

Yes, because clamping works for any axis-aligned rectangle regardless of width or height, ensuring accurate closest-point calculation.

Can the circle be completely inside the rectangle?

Yes, the same distance check confirms overlap even when the circle lies entirely within the rectangle without touching edges.

Why use squared distance instead of Euclidean distance?

Squared distance avoids costly square root operations and preserves correctness for comparing with radius squared, which is efficient for geometry-based checks.

Which pattern does this problem follow?

This problem follows the Math plus Geometry pattern by computing distances from geometric features and handling edge and corner cases precisely.

terminal

Solution

Solution 1: Mathematics

For a point $(x, y)$, its shortest distance to the center of the circle $(xCenter, yCenter)$ is $\sqrt{(x - xCenter)^2 + (y - yCenter)^2}$. If this distance is less than or equal to the radius $radius$, then this point is within the circle (including the boundary).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def checkOverlap(
        self,
        radius: int,
        xCenter: int,
        yCenter: int,
        x1: int,
        y1: int,
        x2: int,
        y2: int,
    ) -> bool:
        def f(i: int, j: int, k: int) -> int:
            if i <= k <= j:
                return 0
            return i - k if k < i else k - j

        a = f(x1, x2, xCenter)
        b = f(y1, y2, yCenter)
        return a * a + b * b <= radius * radius

Continue Practicing

#1453 maximum number of darts inside of a circular dartboard #1515 best position for a service centre #1266 minimum time visiting all points