How do you solve Circle and Rectangle Overlapping on LeetCode?

Circle and Rectangle Overlapping (LeetCode #1401) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(1) space complexity. Key insight: Finding the closest point on the rectangle to the circle's center is key to optimizing the solution.

What is the time complexity of Circle and Rectangle Overlapping?

The optimal solution for Circle and Rectangle Overlapping runs in O(1) time and uses O(1) space. This solution runs in constant time since it only involves a few arithmetic operations regardless of the rectangle's size.

What is the brute force solution for Circle and Rectangle Overlapping?

The brute force approach for Circle and Rectangle Overlapping is Brute Force, with O(n²) time complexity and O(1) space complexity. We can check every point within the rectangle to see if it lies within the circle. This is a straightforward method but can be inefficient if the rectangle is large. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Circle and Rectangle Overlapping?

Circle and Rectangle Overlapping uses the following concepts: Math, Geometry. The recommended patterns to study are: Geometry, Distance Calculation.

What are the interview tips for Circle and Rectangle Overlapping?

Always clarify the problem constraints and edge cases with the interviewer. Explain your thought process clearly as you work through the problem. Consider both brute force and optimized solutions to demonstrate your understanding.

What are common mistakes when solving Circle and Rectangle Overlapping?

Not considering edge cases where the circle's center is outside the rectangle but still overlaps. Confusing the distance formula with the area of the circle.

#1401

Circle and Rectangle Overlapping

Medium

MathGeometryGeometryDistance Calculation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(1)	O(1)

💡

Intuition

Time O(1)Space O(1)

Instead of checking every point, we find the closest point on the rectangle to the circle's center and check if this point is within the circle. This reduces unnecessary calculations.

⚙️

Algorithm

3 steps

1Step 1: Determine the closest point on the rectangle to the circle's center (xCenter, yCenter).
2Step 2: Clamp the circle's center coordinates to the rectangle's boundaries to find the closest point.
3Step 3: Calculate the distance from this closest point to the circle's center and compare it to the radius.

solution.py6 lines

1def checkOverlap(radius, xCenter, yCenter, x1, y1, x2, y2):
2    closestX = max(x1, min(xCenter, x2))
3    closestY = max(y1, min(yCenter, y2))
4    distanceX = closestX - xCenter
5    distanceY = closestY - yCenter
6    return (distanceX ** 2 + distanceY ** 2) <= radius ** 2

ℹ

Complexity note: This solution runs in constant time since it only involves a few arithmetic operations regardless of the rectangle's size.

1Finding the closest point on the rectangle to the circle's center is key to optimizing the solution.
2Understanding the distance formula is crucial for determining overlap.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.