1401. Circle and Rectangle Overlapping - Solution

The problem

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 (x_i, y_i) 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
-10⁴ <= xCenter, yCenter <= 10⁴
-10⁴ <= x1 < x2 <= 10⁴
-10⁴ <= y1 < y2 <= 10⁴

Approach overview

Problem 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 1: Find the Closest Point on the Rectangle to the Circle Center

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.

Python

def is_circle_overlapping_rectangle(radius, x_center, y_center, x1, y1, x2, y2):
    closest_x = max(x1, min(x_center, x2))
    closest_y = max(y1, min(y_center, y2))
    dist_x = x_center - closest_x
    dist_y = y_center - closest_y
    return (dist_x ** 2 + dist_y ** 2) <= (radius ** 2)

print(is_circle_overlapping_rectangle(1, 0, 0, 1, -1, 3, 1))  # True
print(is_circle_overlapping_rectangle(1, 1, 1, 1, -3, 2, -1))  # False
print(is_circle_overlapping_rectangle(1, 0, 0, -1, 0, 0, 1))  # True

Java

public class Main {
    public static boolean isCircleOverlappingRectangle(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        int closestX = Math.max(x1, Math.min(xCenter, x2));
        int closestY = Math.max(y1, Math.min(yCenter, y2));
        int distX = xCenter - closestX;
        int distY = yCenter - closestY;
        return (distX * distX + distY * distY) <= (radius * radius);
    }

    public static void main(String[] args) {
        System.out.println(isCircleOverlappingRectangle(1, 0, 0, 1, -1, 3, 1)); // true
        System.out.println(isCircleOverlappingRectangle(1, 1, 1, 1, -3, 2, -1)); // false
        System.out.println(isCircleOverlappingRectangle(1, 0, 0, -1, 0, 0, 1)); // true
    }
}

C++

#include <iostream>
#include <cmath>

bool isCircleOverlappingRectangle(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
    int closestX = std::max(x1, std::min(xCenter, x2));
    int closestY = std::max(y1, std::min(yCenter, y2));
    int distX = xCenter - closestX;
    int distY = yCenter - closestY;
    return (distX * distX + distY * distY) <= (radius * radius);
}

int main() {
    std::cout << std::boolalpha;
    std::cout << isCircleOverlappingRectangle(1, 0, 0, 1, -1, 3, 1) << std::endl; // true
    std::cout << isCircleOverlappingRectangle(1, 1, 1, 1, -3, 2, -1) << std::endl; // false
    std::cout << isCircleOverlappingRectangle(1, 0, 0, -1, 0, 0, 1) << std::endl; // true
    return 0;
}

JavaScript

function isCircleOverlappingRectangle(radius, xCenter, yCenter, x1, y1, x2, y2) {
    let closestX = Math.max(x1, Math.min(xCenter, x2));
    let closestY = Math.max(y1, Math.min(yCenter, y2));
    let distX = xCenter - closestX;
    let distY = yCenter - closestY;
    return (distX * distX + distY * distY) <= (radius * radius);
}

console.log(isCircleOverlappingRectangle(1, 0, 0, 1, -1, 3, 1));  // true
console.log(isCircleOverlappingRectangle(1, 1, 1, 1, -3, 2, -1));  // false
console.log(isCircleOverlappingRectangle(1, 0, 0, -1, 0, 0, 1));  // true

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool isCircleOverlappingRectangle(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
    int closestX = (xCenter < x1) ? x1 : (xCenter > x2 ? x2 : xCenter);
    int closestY = (yCenter < y1) ? y1 : (yCenter > y2 ? y2 : yCenter);
    int distX = xCenter - closestX;
    int distY = yCenter - closestY;
    return (distX * distX + distY * distY) <= (radius * radius);
}

int main() {
    printf("%d\n", isCircleOverlappingRectangle(1, 0, 0, 1, -1, 3, 1)); // Output: 1 (true)
    printf("%d\n", isCircleOverlappingRectangle(1, 1, 1, 1, -3, 2, -1)); // Output: 0 (false)
    printf("%d\n", isCircleOverlappingRectangle(1, 0, 0, -1, 0, 0, 1)); // Output: 1 (true)
    return 0;
}

using System;

public class Program {
    public static bool IsCircleOverlappingRectangle(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        int closestX = Math.Max(x1, Math.Min(xCenter, x2));
        int closestY = Math.Max(y1, Math.Min(yCenter, y2));
        int distX = xCenter - closestX;
        int distY = yCenter - closestY;
        return (distX * distX + distY * distY) <= (radius * radius);
    }

    public static void Main() {
        Console.WriteLine(IsCircleOverlappingRectangle(1, 0, 0, 1, -1, 3, 1)); // true
        Console.WriteLine(IsCircleOverlappingRectangle(1, 1, 1, 1, -3, 2, -1)); // false
        Console.WriteLine(IsCircleOverlappingRectangle(1, 0, 0, -1, 0, 0, 1)); // true
    }
}

This Python function determines the overlap by finding the closest point on the rectangle to the circle's center and then measuring the squared distance to check for overlap.

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Check Each Rectangle Edge for Circle Intersection

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.

Python

/* Python provides ample libraries or manual geometry for detailed overlap check of circle with rectangle edges */

Java

/* The detailed edge-inspection implementation would be similarly developed in a Java environment */

C++

/* Develop this structure for a solution using line-rectangle intersection in C++ */

JavaScript

/* JavaScript mappings of geometrical principles allow for potential edge-interaction solutions for the described task */

/* You may expand this function to implement the circle-rectangle edge intersection method in C */

/* Edge-check tactical assessment can be fit using or by considerations within C# capabilities */

The edge-based intersection exploit concerns using Python capabilities for practical intersection deducing from geometrical principles. Extend as needed.

Complexity

Similar bounded O(1) characteristics follow as edge checks form a constant-time invariant.

Try this approach in the editor

Approach 3: 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).

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]:

If x_1 leq xCenter leq x_2, then the minimum value of |x - xCenter| is 0;
If xCenter < x_1, then the minimum value of |x - xCenter| is x_1 - xCenter;
If 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.

TypeScript

function checkOverlap(
    radius: number,
    xCenter: number,
    yCenter: number,
    x1: number,
    y1: number,
    x2: number,
    y2: number,
): boolean {
    const f = (i: number, j: number, k: number) => {
        if (i <= k && k <= j) {
            return 0;
        }
        return k < i ? i - k : k - j;
    };
    const a = f(x1, x2, xCenter);
    const b = f(y1, y2, yCenter);
    return a * a + b * b <= radius * radius;
}

func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
	f := func(i, j, k int) int {
		if i <= k && k <= j {
			return 0
		}
		if k < i {
			return i - k
		}
		return k - j
	}
	a := f(x1, x2, xCenter)
	b := f(y1, y2, yCenter)
	return a*a+b*b <= radius*radius
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Find the Closest Point on the Rectangle to the Circle Center	Time Complexity: O(1) Space Complexity: O(1)
Check Each Rectangle Edge for Circle Intersection	Similar bounded O(1) characteristics follow as edge checks form a constant-time invariant.
Mathematics	–

Complexity analysis

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.

Frequently asked questions

Is Circle and Rectangle Overlapping easy or hard?

The problem is rated Medium on LeetCode. The logic is short once you recognize the closest-point projection idea, but many candidates initially overcomplicate it by checking edges and corners separately.

Circle and Rectangle Overlapping Python/Java solution

Most implementations compute the closest point using clamp logic and then check squared distance. The same idea translates directly across Python, Java, C++, C#, JavaScript, and C because it uses only comparisons and integer arithmetic.

How to solve Circle and Rectangle Overlapping in O(1)?

Clamp the circle center coordinates to the rectangle bounds: compute closestX = max(x1, min(xCenter, x2)) and closestY = max(y1, min(yCenter, y2)). Then calculate the squared distance between (xCenter, yCenter) and (closestX, closestY). If the distance is less than or equal to radius squared, the circle overlaps the rectangle.

What is the best approach for Circle and Rectangle Overlapping?

The closest-point clamp method is the most reliable approach. Clamp the circle center coordinates to the rectangle boundaries to find the nearest point on the rectangle, then compare the squared distance to the circle radius squared. This runs in O(1) time and O(1) space and avoids handling separate edge and corner cases.

Is Circle and Rectangle Overlapping asked at Google/Amazon/Meta?

Geometry and coordinate problems like this appear in interviews at companies such as Google, Amazon, and Meta, especially in roles involving graphics, simulations, or spatial reasoning. The problem tests mathematical reasoning and careful boundary handling.

What data structure is used in Circle and Rectangle Overlapping?

No specialized data structure is required. The solution relies on coordinate arithmetic, boundary clamping, and squared distance calculations using basic math and geometry concepts.

What is the time complexity of Circle and Rectangle Overlapping?

The optimal solution runs in O(1) time and O(1) space. Only a few arithmetic operations and comparisons are required to compute the closest point and check the squared distance against the radius.

Circle and Rectangle Overlapping solution and explanation

The problem

Approach overview

Approach 1: Find the Closest Point on the Rectangle to the Circle Center

Approach 2: Check Each Rectangle Edge for Circle Intersection

Approach 3: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Circle and Rectangle Overlapping solution and explanation

The problem

Approach overview

Approach 1: Find the Closest Point on the Rectangle to the Circle Center

Approach 2: Check Each Rectangle Edge for Circle Intersection

Approach 3: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems