Leetcode 1401. Circle and Rectangle Overlapping

Problem Explanation

In this problem, we have a circle and an axis-aligned rectangle. The task is to determine if the circle and rectangle overlap. This is defined as there being at least one point that belongs to both the circle and the rectangle.

To illustrate, let's use the following example:

Example: radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1

The circle's radius is 1 and is centered at the origin (0,0). The rectangle has its bottom-left corner at (1,-1) and its top-right corner at (3,1). The point (1,0) is common to both the circle and the rectangle, hence they overlap.

The circle and rectangle are represented using their geometric parameters: the circle by its radius and center coordinates (radius, x_center, y_center) and the rectangle by the coordinates of its bottom-left and top-right corners (x1, y1, x2, y2).

Solution Approach

The solution uses the method of finding the nearest point within the rectangle to the circle's center and then comparing the distance to the circle's radius.

This solution works by 'clamping' the center of the circle in the range defined by the rectangle. Clamping here refers to ensuring the circle’s center coordinates fall within the x and y ranges defined by the rectangle corners. This gives us the closest point within the rectangle to the circle's center.

Then we calculate the square of the euclidian distance between the circle's center and the closest rectangle point. We don't take the square root for the distance to avoid unnecessary computation since we are comparing it to the square of the radius.

Finally, if the calculated distance is less than or equal to the square of the radius, we return True, indicating that the circle and rectangle do overlap, else we return False.

Python Solution

1
2python
3class Solution(object):
4    def checkOverlap(self, radius, x_center, y_center, x1, y1, x2, y2):
5        # Ensure x_center and y_center fall within the rectangle range
6        closestX = max(x1, min(x2, x_center)) 
7        closestY = max(y1, min(y2, y_center))
8
9        # Calculate the squares of distances 
10        distanceX = x_center - closestX
11        distanceY = y_center - closestY
12
13        # Check if the distance is within the circle's radius
14        return (distanceX * distanceX) + (distanceY * distanceY) <= (radius * radius)

Java Solution

1
2java
3class Solution {
4    public boolean checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
5        // Ensure x_center and y_center fall within the rectangle range
6        int closestX = Math.max(x1, Math.min(x2, x_center));
7        int closestY = Math.max(y1, Math.min(y2, y_center));
8
9        // Calculate the squares of distances
10        int distanceX = x_center - closestX;
11        int distanceY = y_center - closestY;
12
13        // Check if the distance is within the circle's radius
14        return (distanceX * distanceX) + (distanceY * distanceY) <= (radius * radius);
15    }
16}

JavaScript Solution

1
2javascript
3class Solution {
4    checkOverlap(radius, x_center, y_center, x1, y1, x2, y2) {
5        // Ensure x_center and y_center fall within the rectangle range
6        let closestX = Math.max(x1, Math.min(x2, x_center));
7        let closestY = Math.max(y1, Math.min(y2, y_center));
8
9        // Calculate the squares of distances
10        let distanceX = x_center - closestX;
11        let distanceY = y_center - closestY;
12
13        // Check if the distance is within the circle's radius
14        return (distanceX * distanceX) + (distanceY * distanceY) <= (radius * radius);
15    }
16}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
6        // Ensure x_center and y_center fall within the rectangle range
7        int closestX = max(x1, min(x2, x_center));
8        int closestY = max(y1, min(y2, y_center));
9
10        // Calculate the squares of distances
11        int distanceX = x_center - closestX;
12        int distanceY = y_center - closestY;
13
14        // Check if the distance is within the circle's radius
15        return (distanceX * distanceX) + (distanceY * distanceY) <= (radius * radius);
16    }
17};

C# Solution

1
2cs
3public class Solution {
4    public bool CheckOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
5        // Ensure x_center and y_center fall within the rectangle range
6        int closestX = Math.Max(x1, Math.Min(x2, x_center));
7        int closestY = Math.Max(y1, Math.Min(y2, y_center));
8
9        // Calculate the squares of distances
10        int distanceX = x_center - closestX;
11        int distanceY = y_center - closestY;
12
13        // Check if the distance is within the circle's radius
14        return (distanceX * distanceX) + (distanceY * distanceY) <= (radius * radius);
15    }
16}

That's it. By clamping the circle's center inside the rectangle's area and then comparing the distance from this point to the circle's center with the circle's radius, we can easily determine whether the circle and rectangle overlap or not.This solution is highly efficient as it only involves basic mathematical calculations and a couple of simple comparisons, leading to a time complexity of O(1) and a space complexity of O(1).

Certain things to note about this solution:

  1. We use the squared distance and squared radius for comparison instead of taking the square root. This is because square root operations are computationally more expensive. Furthermore, since we are only interested in drawing a comparison rather than the actual distance, squaring both values won't affect the result.

  2. We clamp the values within two function calls, max and min, ensuring the selected coordinate lies within the rectangle. This gets us the closest point in the rectangle to the circle's center.

In conclusion, the given problem can be solved with a straight-forward geometry-based approach. We use clamping to find the closest point in the rectangle to the circle's center, and then check if the circle's radius is sufficient to reach that point. This aproach is applicable in all languages with built-in min, max functions and support for basic operations like addition, subtraction, and multiplication. Python, JavaScript, Java, C++, and C# are perfect examples, as shown in the code snippets above.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫