Circle and Rectangle Overlapping — Problem & Solution
Circle and Rectangle Overlapping solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Circle and Rectangle Overlapping is a medium coding problem on math and geometry, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Math, Geometry
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A circle has centre (xCenter, yCenter) and radius radius. An axis-aligned rectangle has bottom-left corner (x1, y1) and top-right corner (x2, y2).
Both shapes are closed: the circle includes its boundary and so does the rectangle. Return true if there is at least one point that belongs to both shapes — touching at a single point counts.
Example 1
Input: radius = 2, xCenter = 0, yCenter = 0, x1 = 2, y1 = -3, x2 = 6, y2 = 1
Output: true
Explanation: The shapes touch at (2, 0).
Example 2
Input: radius = 5, xCenter = 0, yCenter = 0, x1 = 3, y1 = 4, x2 = 8, y2 = 9
Output: true
Explanation: The corner (3, 4) is exactly 5 away from the centre.
Example 3
Input: radius = 1, xCenter = 1, yCenter = 1, x1 = -3, y1 = 3, x2 = -1, y2 = 5
Output: false
Constraints
1 <= radius <= 2000-10^4 <= xCenter, yCenter <= 10^4-10^4 <= x1 < x2 <= 10^4-10^4 <= y1 < y2 <= 10^4
Hints for Circle and Rectangle Overlapping
Hint 1
The shapes meet exactly when the rectangle point closest to the centre lies inside the circle.
Hint 2
The closest point can be found one axis at a time.
Hint 3
Clamp
xCenterinto[x1, x2]andyCenterinto[y1, y2], then compare squared distances so everything stays an integer.
How to solve Circle and Rectangle Overlapping
The circle and the rectangle share a point exactly when the distance from the centre to the rectangle is at most the radius, and the nearest rectangle point is the centre clamped into the rectangle.
Approach
- Let
nx = min(max(xCenter, x1), x2)andny = min(max(yCenter, y1), y2)— the rectangle point nearest the centre. - Let
dx = nx - xCenteranddy = ny - yCenter. - Return
dx² + dy² <= radius².
Why it works
The squared distance from the centre to a rectangle point (x, y) is (x - xCenter)² + (y - yCenter)², and the two terms can be minimised independently because the rectangle is a product of an x-interval and a y-interval. The closest value in an interval to a number is that number clamped into the interval. If even the closest point is farther than the radius, no rectangle point is in the circle; if it is within the radius, that point is in both shapes.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Checking only whether a rectangle corner is in the circle, or the centre is in the rectangle, misses a circle that crosses an edge's middle.
- Use
<=: touching counts as overlapping. - Compare squared values — a floating-point square root can misjudge the tangent cases.
Reference solution
Python
def checkOverlap(radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
nx = min(max(xCenter, x1), x2)
ny = min(max(yCenter, y1), y2)
dx = nx - xCenter
dy = ny - yCenter
return dx * dx + dy * dy <= radius * radiusJava
public static boolean checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
int nx = Math.min(Math.max(xCenter, x1), x2);
int ny = Math.min(Math.max(yCenter, y1), y2);
long dx = nx - xCenter;
long dy = ny - yCenter;
return dx * dx + dy * dy <= (long) radius * radius;
}C++
bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
int nx = min(max(xCenter, x1), x2);
int ny = min(max(yCenter, y1), y2);
long long dx = nx - xCenter;
long long dy = ny - yCenter;
return dx * dx + dy * dy <= (long long) radius * radius;
}JavaScript
var checkOverlap = function(radius, xCenter, yCenter, x1, y1, x2, y2) {
var nx = Math.min(Math.max(xCenter, x1), x2);
var ny = Math.min(Math.max(yCenter, y1), y2);
var dx = nx - xCenter;
var dy = ny - yCenter;
return dx * dx + dy * dy <= radius * radius;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.