Watch 9 video solutions for Circle and Rectangle Overlapping, a medium level problem involving Math, Geometry. This walkthrough by Leet Kodee has 560 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |