You are given a circle represented as (radius, xCenter, yCenter) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.
Return true if the circle and rectangle are overlapped otherwise return false. In other words, check if there is any point (xi, yi) that belongs to the circle and the rectangle at the same time.
Example 1:
Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1 Output: true Explanation: 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 3:
Input: radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1 Output: true
Constraints:
1 <= radius <= 2000-104 <= xCenter, yCenter <= 104-104 <= x1 < x2 <= 104-104 <= y1 < y2 <= 104Problem Overview: You are given a circle defined by its radius and center (xCenter, yCenter), and an axis-aligned rectangle defined by (x1, y1) and (x2, y2). The task is to determine whether the circle and rectangle overlap at any point.
Approach 1: Check Each Rectangle Edge for Circle Intersection (O(1) time, O(1) space)
Treat the rectangle as four line segments and check whether the circle intersects any edge. For each edge, compute the shortest distance from the circle center to the segment. If that distance is less than or equal to the radius, the circle intersects the rectangle. You must also check rectangle corners because the closest point might be a vertex instead of a point along the edge. This approach relies on basic geometry formulas for point-to-segment distance and squared distance comparison.
Approach 2: Find the Closest Point on the Rectangle to the Circle Center (O(1) time, O(1) space)
The key observation: if the rectangle and circle overlap, the closest point on the rectangle to the circle's center must lie inside the circle. Compute this closest point by clamping the center coordinates to the rectangle bounds: closestX = clamp(xCenter, x1, x2) and closestY = clamp(yCenter, y1, y2). Then calculate the squared distance between (xCenter, yCenter) and (closestX, closestY). If it is less than or equal to radius^2, an overlap exists. This works because any point outside the rectangle projects to the nearest boundary point. The solution uses simple math operations and avoids explicitly checking edges or corners.
Recommended for interviews: The closest-point clamp approach. It reduces the geometry to a few comparisons and a squared distance check, making the implementation short and reliable. Interviewers typically expect this solution because it shows you understand geometric projection and boundary clamping. The edge-intersection approach demonstrates geometric reasoning but requires more cases and is easier to implement incorrectly.
To determine if the circle and rectangle overlap, we need to find the closest point on the rectangle to the circle's center. This point can be inside or on the rectangle. Once we have the closest point, calculate the distance from this point to the circle's center. If this distance is less than or equal to the circle's radius, the two shapes overlap.
This approach involves finding the point on the rectangle that is closest to the circle's center using the clamp method.
This C implementation uses the clamp method to find the closest point on the rectangle to the circle's center and checks if the distance to that point is within the circle's radius.
Time Complexity: O(1) because calculations are performed in constant time.
Space Complexity: O(1) since no additional space is used.
Another approach is to consider each edge of the rectangle and determine if there is any intersection with the circle. The circle can overlap with the rectangle if it intersects any of its edges. This method involves checking each edge of the rectangle to see if it is within the circle's radius from the circle's center.
Please implement the edge intersection checking manually as current context provides a basic clamp-based solution. Here, the intersection would involve bounding lines around the rectangle and checking for circle intersection.
Due to lack of detail, complexity is not provided directly but would usually be O(1) for fixed number of edge checks, and O(1) space usage similarly.
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).
For points within the rectangle (including the boundary), their x-coordinates x satisfy x_1 leq x leq x_2, and their y-coordinates y satisfy y_1 leq y leq y_2. To determine whether the circle and rectangle overlap, we need to find a point (x, y) within the rectangle such that a = |x - xCenter| and b = |y - yCenter| are minimized. If a^2 + b^2 leq radius^2, then the circle and rectangle overlap.
Therefore, the problem is transformed into finding the minimum value of a = |x - xCenter| when x \in [x_1, x_2], and the minimum value of b = |y - yCenter| when y \in [y_1, y_2].
For x \in [x_1, x_2]:
x_1 leq xCenter leq x_2, then the minimum value of |x - xCenter| is 0;xCenter < x_1, then the minimum value of |x - xCenter| is x_1 - xCenter;xCenter > x_2, then the minimum value of |x - xCenter| is xCenter - x_2.Similarly, we can find the minimum value of |y - yCenter| when y \in [y_1, y_2]. We can use a function f(i, j, k) to handle the above situations.
That is, a = f(x_1, x_2, xCenter), b = f(y_1, y_2, yCenter). If a^2 + b^2 leq radius^2, then the circle and rectangle overlap.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Find the Closest Point on the Rectangle to the Circle Center | Time Complexity: O(1) because calculations are performed in constant time. |
| Check Each Rectangle Edge for Circle Intersection | Due to lack of detail, complexity is not provided directly but would usually be O(1) for fixed number of edge checks, and O(1) space usage similarly. |
| Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Check Each Rectangle Edge for Circle Intersection | O(1) | O(1) | Useful when implementing general circle–segment intersection logic or when rectangles are treated as four independent edges. |
| Closest Point on Rectangle to Circle Center (Clamp Method) | O(1) | O(1) | Best general solution for axis-aligned rectangles. Minimal code and fewer geometric edge cases. |
LeetCode 1401 || Circle and Rectangle Overlapping • Leet Kodee • 560 views views
Watch 8 more video solutions →Practice Circle and Rectangle Overlapping with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor