Circle and Rectangle Overlapping - Practice Coding Problems

Circle and Rectangle Overlapping - Problem

Math Geometry Hard

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 (xi, yi) that belongs to the circle and the rectangle at the same time.

Input & Output

Example 1 — Circle Overlapping Rectangle

$ Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1

› Output: true

💡 Note: Circle at (0,0) with radius 1 overlaps the rectangle. The closest point on rectangle to circle center is (1,0), and distance = 1 which equals the radius, so they overlap.

Example 2 — Circle Not Overlapping Rectangle

$ Input: radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1

› Output: false

💡 Note: Circle at (1,1) with radius 1 does not reach the rectangle. The closest point on rectangle is (1,-1), distance = 2 > radius 1, so no overlap.

Example 3 — Circle Contains Rectangle

$ Input: radius = 5, xCenter = 0, yCenter = 0, x1 = -1, y1 = -1, x2 = 1, y2 = 1

› Output: true

💡 Note: Large circle with radius 5 completely contains the small rectangle, so they definitely overlap.

Constraints

1 ≤ radius ≤ 2000
-10⁴ ≤ xCenter, yCenter ≤ 10⁴
-10⁴ ≤ x1 < x2 ≤ 10⁴
-10⁴ ≤ y1 < y2 ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Circle (center, radius) and Rectangle (bottom-left, top-right)

Process

Find closest point on rectangle to circle center

Output

Return true if distance ≤ radius, false otherwise

Key Takeaway

🎯 Key Insight: The optimal solution uses coordinate clamping to find the closest rectangle point to the circle center in O(1) time

Asked in

G Google 15 🍎 Apple 12 M Microsoft 8

The key insight is to find the closest point on the rectangle to the circle's center using coordinate clamping, then check if this distance is within the circle's radius. Best approach is Mathematical Closest Point with Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Closest Point	O(1)	O(1)	Find closest point on rectangle to circle center and check distance
Brute Force Point Sampling	O(n²)	O(1)	Sample grid points and check if any belong to both shapes

Mathematical Closest Point — Algorithm Steps

Find closest point on rectangle to circle center by clamping coordinates
Calculate distance from circle center to this closest point
Compare distance with circle radius
Return true if distance ≤ radius

Visualization

Tap to expand

Step-by-Step Walkthrough

Clamp Coordinates

Find closest point on rectangle boundary

Calculate Distance

Measure distance from circle center to closest point

Compare with Radius

Check if distance ≤ radius for overlap

Code -

solution.c — C

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

int min_int(int a, int b) {
    return a < b ? a : b;
}

int max_int(int a, int b) {
    return a > b ? a : b;
}

bool solution(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
    // Find the closest point on the rectangle to the circle center
    // Clamp the circle center coordinates to the rectangle bounds
    int closestX = max_int(x1, min_int(xCenter, x2));
    int closestY = max_int(y1, min_int(yCenter, y2));
    
    // Calculate the distance from circle center to closest point
    long long dx = xCenter - closestX;
    long long dy = yCenter - closestY;
    long long distanceSquared = dx * dx + dy * dy;
    
    // Check if this distance is within the circle radius
    return distanceSquared <= (long long)radius * radius;
}

int main() {
    int radius, xCenter, yCenter, x1, y1, x2, y2;
    scanf("%d", &radius);
    scanf("%d", &xCenter);
    scanf("%d", &yCenter);
    scanf("%d", &x1);
    scanf("%d", &y1);
    scanf("%d", &x2);
    scanf("%d", &y2);
    
    bool result = solution(radius, xCenter, yCenter, x1, y1, x2, y2);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Only performs constant number of mathematical operations

✓ Linear Growth

Space Complexity

O(1)

Uses only constant extra variables for calculations

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Closest Point — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler