Circle and Rectangle Overlapping

Medium
1304.

Circle and Rectangle Overlapping

Circle and Rectangle Overlapping is a medium coding problem on math and geometry, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} radius
 * @param {number} xCenter
 * @param {number} yCenter
 * @param {number} x1
 * @param {number} y1
 * @param {number} x2
 * @param {number} y2
 * @return {boolean}
 */
var checkOverlap = function(radius, xCenter, yCenter, x1, y1, x2, y2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    The shapes meet exactly when the rectangle point closest to the centre lies inside the circle.

  2. Hint 2

    The closest point can be found one axis at a time.

  3. Hint 3

    Clamp xCenter into [x1, x2] and yCenter into [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

  1. Let nx = min(max(xCenter, x1), x2) and ny = min(max(yCenter, y1), y2) — the rectangle point nearest the centre.
  2. Let dx = nx - xCenter and dy = ny - yCenter.
  3. 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 * radius

Java

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.

All 337 math problems · the whole catalogue