Problem Description

You are given a circle and a rectangle on a 2D plane. The circle is defined by its radius and center coordinates (xCenter, yCenter). The rectangle is axis-aligned (its sides are parallel to the x and y axes) and defined by two corners: (x1, y1) as the bottom-left corner and (x2, y2) as the top-right corner.

Your task is to determine if the circle and rectangle overlap. They overlap if there exists at least one point that belongs to both the circle and the rectangle simultaneously. Points on the boundaries of both shapes are considered to be inside them.

Return true if the circle and rectangle overlap, otherwise return false.

For example, if a circle has radius 2 and center at (1, 1), and a rectangle has corners at (0, 0) and (3, 3), they would overlap because there are points that exist within both shapes. The key insight is to find the closest point on (or inside) the rectangle to the circle's center - if this distance is less than or equal to the radius, then the shapes overlap.

Intuition

To determine if a circle and rectangle overlap, we need to find if any point exists in both shapes. Instead of checking every point, we can think about this problem in reverse - what's the closest point on the rectangle to the circle's center?

If the closest point on the rectangle to the circle's center is within the radius distance, then the shapes must overlap. This transforms our problem into finding the minimum distance from the circle's center to any point on or inside the rectangle.

For any point inside or on the rectangle, its x-coordinate must be in the range [x1, x2] and its y-coordinate must be in the range [y1, y2]. To minimize the distance to the circle's center (xCenter, yCenter), we need to find the x and y coordinates that minimize |x - xCenter| and |y - yCenter| respectively.

For the x-coordinate:

• If xCenter falls within [x1, x2], the minimum distance in the x-direction is 0 (we can choose x = xCenter)
• If xCenter < x1, the closest x-coordinate is x1, giving distance x1 - xCenter
• If xCenter > x2, the closest x-coordinate is x2, giving distance xCenter - x2

The same logic applies for the y-coordinate. Once we have the minimum distances in both directions (let's call them a and b), the closest point on the rectangle to the circle's center has distance sqrt(a² + b²) from the center.

The circle and rectangle overlap if and only if this minimum distance is less than or equal to the radius, which gives us the condition: a² + b² ≤ radius².

Learn more about Math patterns.

Solution Approach

The implementation follows the mathematical approach we derived from the intuition. We need to find the minimum distance from the circle's center to the rectangle in both x and y directions.

We create a helper function f(i, j, k) that computes the minimum distance from a point k to an interval [i, j]:

• If i ≤ k ≤ j, the point is within the interval, so the minimum distance is 0
• If k < i, the point is to the left of the interval, so the minimum distance is i - k
• If k > j, the point is to the right of the interval, so the minimum distance is k - j

This function elegantly handles all three cases for finding the closest point on an interval to a given point.

In the main function:

1. We calculate a = f(x1, x2, xCenter) - this gives us the minimum distance from xCenter to the x-interval [x1, x2]
2. We calculate b = f(y1, y2, yCenter) - this gives us the minimum distance from yCenter to the y-interval [y1, y2]
3. We check if a² + b² ≤ radius²

The key insight is that a and b represent the x and y components of the shortest vector from the circle's center to the rectangle. If we were to draw a line from the circle's center to the closest point on the rectangle, a would be the horizontal component and b would be the vertical component of that line.

By using the Pythagorean theorem, a² + b² gives us the square of the actual distance from the circle's center to the closest point on the rectangle. We compare this with radius² (avoiding the square root calculation for efficiency) to determine if the shapes overlap.

The time complexity is O(1) since we only perform constant-time arithmetic operations. The space complexity is also O(1) as we only use a few variables.

Example Walkthrough

Let's walk through an example with a circle centered at (4, 2) with radius 3, and a rectangle with bottom-left corner at (1, 0) and top-right corner at (3, 4).

Step 1: Find the minimum x-distance

• Circle's x-center: 4
• Rectangle's x-range: [1, 3]
• Since 4 > 3, the circle center is to the right of the rectangle
• Minimum x-distance: a = 4 - 3 = 1

Step 2: Find the minimum y-distance

• Circle's y-center: 2
• Rectangle's y-range: [0, 4]
• Since 0 ≤ 2 ≤ 4, the circle center's y-coordinate is within the rectangle's range
• Minimum y-distance: b = 0

Step 3: Check overlap condition

• We need to check if a² + b² ≤ radius²
• a² + b² = 1² + 0² = 1
• radius² = 3² = 9
• Since 1 ≤ 9, the condition is satisfied

Result: The circle and rectangle overlap (return true)

To visualize: The closest point on the rectangle to the circle's center is (3, 2) - the right edge of the rectangle at the same y-coordinate as the circle's center. The distance from (4, 2) to (3, 2) is 1, which is less than the radius of 3, confirming the overlap.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The algorithm performs a constant number of operations regardless of input size:

• The helper function f is called exactly twice (once for x-coordinate and once for y-coordinate)
• Each call to f performs at most 2 comparisons and 1 arithmetic operation
• The final calculation involves 2 multiplications, 1 addition, and 1 comparison
• All operations are basic arithmetic/comparison operations that take constant time

Therefore, the overall time complexity is O(1).

Space Complexity: O(1)

The algorithm uses only a fixed amount of extra space:

• Two integer variables a and b to store the results of function f
• No additional data structures are created
• The helper function f uses only its parameters and doesn't allocate any extra space
• The space usage doesn't depend on the input size

Therefore, the overall space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Calculating Distance When Circle Center is Inside Rectangle

Pitfall: A common mistake is to assume that if the circle's center is inside the rectangle, we need to check distances to all four edges or corners. This leads to unnecessary complexity and potential errors.

Why it happens: Developers might overthink the problem and try to handle the "center inside rectangle" case separately with complex edge/corner checking logic.

Correct approach: The solution elegantly handles this case automatically. When the circle center is inside the rectangle, both horizontal_distance and vertical_distance become 0 (since the center's coordinates fall within both ranges). This results in squared_distance = 0, which is always ≤ radius², correctly returning true.

2. Using Euclidean Distance to Rectangle Edges Instead of Closest Point

Pitfall: Calculating the distance from the circle center to each of the four edges of the rectangle and taking the minimum, which doesn't account for corner cases correctly.

# INCORRECT approach
def checkOverlap_wrong(self, radius, xCenter, yCenter, x1, y1, x2, y2):
    # This incorrectly calculates distances to edges
    dist_to_left = abs(xCenter - x1)
    dist_to_right = abs(xCenter - x2)
    dist_to_bottom = abs(yCenter - y1)
    dist_to_top = abs(yCenter - y2)
  
    min_dist = min(dist_to_left, dist_to_right, dist_to_bottom, dist_to_top)
    return min_dist <= radius  # WRONG!

Why it's wrong: This approach fails when the closest point to the circle center is a corner of the rectangle. For example, if the circle center is diagonally away from a corner, the actual distance should be calculated using both x and y components, not just the minimum of individual edge distances.

Solution: The correct approach finds the closest point on the rectangle (which could be on an edge, at a corner, or inside if the center is within the rectangle) by independently finding the closest x-coordinate and y-coordinate, then combining them using the Pythagorean theorem.

3. Floating Point Precision Issues with Square Root

Pitfall: Using square root operations and comparing floating-point numbers:

# RISKY approach due to floating point precision
import math

def checkOverlap_risky(self, radius, xCenter, yCenter, x1, y1, x2, y2):
    # ... calculate horizontal_distance and vertical_distance ...
  
    actual_distance = math.sqrt(horizontal_distance ** 2 + vertical_distance ** 2)
    return actual_distance <= radius  # Potential precision issues!

Why it's problematic: Floating-point arithmetic can introduce rounding errors, especially with square root operations. This might cause edge cases where shapes that barely touch to be incorrectly classified.

Solution: The provided solution avoids this by comparing squared values (squared_distance <= squared_radius), which keeps all calculations in integer arithmetic (assuming integer inputs) and avoids precision issues entirely.