1401. Circle and Rectangle Overlapping

MediumGeometryMath

Problem Description

You are given a circle and an axis-aligned rectangle. The circle is defined by its radius and the coordinates of its center (xCenter, yCenter). The rectangle is defined by the coordinates of its bottom-left corner (x1, y1) and its top-right corner (x2, y2). Your task is to determine if there exists at least one point that is inside both the given circle and rectangle. The problem is asking you to return true if such a point exists (meaning the circle and rectangle overlap), and false otherwise.

Intuition

To solve this problem, let's first understand the scenarios where a circle and a rectangle can overlap:

Any corner of the rectangle is inside the circle.
Any part of the circle's circumference intersects the rectangle.
The circle is entirely inside the rectangle, or vice versa.

However, checking every point on the circumference directly would be impractical. The key insight here is that the closest point on the rectangle to the circle's center can indicate whether they overlap without checking every point. If this closest point is also inside the circle, then they overlap.

The solution code uses a helper function f to find the closest point on the rectangle to a given point (xCenter, yCenter). The function f calculates the minimum distance along the x or y dimension from the rectangle to the center of the circle. If the center of the circle is within the bounds of the rectangle along one axis, then the minimum distance is 0 for that axis. Otherwise, f returns the distance to the closest edge of the rectangle along that axis.

Once we calculate the minimum distances a and b for the x and y axes, the point on the rectangle closest to the circle's center is at (xCenter + a, yCenter + b). If that point is within the circle (meaning the sum of squares a * a + b * b is less than or equal to radius * radius), then we have an overlap, and the function returns true. If the closest point is outside the circle, the function returns false.

This approach effectively checks whether the rectangle and the circle overlap by considering only the closest point on the rectangle to the circle's center, greatly simplifying the problem.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Solution Approach

The solution employs a straightforward geometric approach, converting the overlap problem into one of measuring distances and comparing them to the circle's radius. Here's how it's implemented:

Function Declaration: The Solution class contains a method checkOverlap which takes as its arguments the circle's radius and its center coordinates, along with the coordinates of the rectangle's bottom-left and top-right corners.
Distance Function (f): The method uses a nested helper function f, which is designed to calculate the shortest one-dimensional distance from a point (either xCenter or yCenter) to an interval defined by two bounds (either x1, x2 or y1, y2). The bounds represent the sides of the rectangle along one axis.
- It works as follows: if the center coordinate (for one dimension) is between the rectangle's edge coordinates, then the circle's center is directly above or alongside the edge (when projected onto that axis), and thus the shortest distance is 0.
- If the circle's center is outside the rectangle along that axis, the function returns the distance to the nearest edge.
Finding the Closest Point: The checkOverlap method then calls f for both the x and y dimensions to find the x-distance (a) and y-distance (b) from the circle’s center to the rectangle's closest edge or point.
Checking Overlap: After the closest point is identified by its x and y distances to the circle's center, we check if this point is inside the circle. The point lies inside if the sum of the squares of the distances a * a + b * b does not exceed the square of the radius of the circle radius * radius.
Returning the Result: Finally, the checkOverlap method returns true if the closest point is inside the circle (hence, an overlap) or false otherwise.

This algorithm is particularly effective because it reduces a 2D problem into a comparative evaluation of calculated 1D distances. No looping or complex structures are necessary, making the solution very efficient in terms of time complexity, which is O(1), as the calculations are done in a fixed number of steps regardless of input size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsetsGenerating random numbersGenerating permutationsSorting integers

Example Walkthrough

Let's go through a small example to illustrate the solution approach.

Assume we are given the following inputs:

Radius of the circle (radius): 2
Coordinates of the circle's center (xCenter, yCenter): (2, 2)
Coordinates of the bottom-left corner of the rectangle (x1, y1): (3, 1)
Coordinates of the top-right corner of the rectangle (x2, y2): (5, 3)

Now, we need to determine if at least one point on the rectangle is also inside the circle.

Following the solution approach:

We start by preparing to invoke the checkOverlap method from the Solution class, which will take our given inputs.
Next, we use the helper function f to calculate the closest x-distance (a) from the circle's center to the rectangle's closest edge.
- In this case, the xCenter is 2, and the x bounds of the rectangle are 3 and 5. Since the xCenter is less than x1, the shortest x-distance to the rectangle is x1 - xCenter, which is 3 - 2 = 1.
We apply the same logic to find the closest y-distance (b) from the circle's center to the rectangle's closest edge.
- The yCenter is 2, and the y bounds are 1 and 3. Since the yCenter is within these bounds, the circle's center is directly alongside the rectangle on the y-axis, so the shortest y-distance is 0.
With the closest x-distance (a) as 1 and the closest y-distance (b) as 0, we now determine whether the closest point on the rectangle to the circle's center is inside the circle.
- We calculate a * a + b * b which equals 1 * 1 + 0 * 0 = 1.
- The square of the circle's radius is radius * radius or 2 * 2 = 4.
Since 1 (the sum of squares of the distances) is less than 4 (the square of the radius), the closest point on the rectangle to the circle's center is within the circle. Therefore, there is an overlap.
The checkOverlap method would return true for these inputs, indicating that the rectangle and the circle do indeed overlap.

This example shows that you do not need to check every point on the rectangle or circle to see if there is an overlap. Instead, by cleverly using the closest point and comparing distance squared, we can efficiently solve the problem with a constant time algorithm.

Solution Implementation

1class Solution:
2    def checkOverlap(
3        self, 
4        radius: int, 
5        x_center: int, 
6        y_center: int, 
7        x1: int, 
8        y1: int, 
9        x2: int, 
10        y2: int
11    ) -> bool:
12        # Helper function to calculate distance from center to rectangle edge
13        # along one dimension (either 'x' or 'y').
14        def distance_to_edge(min_edge: int, max_edge: int, center: int) -> int:
15            # If center is between the edges, the distance is 0.
16            if min_edge <= center <= max_edge:
17                return 0
18            # If center is less than the minimum edge, return distance to the minimum edge.
19            if center < min_edge:
20                return min_edge - center
21            # If center is greater than the maximum edge, return distance to the maximum edge.
22            return center - max_edge
23      
24        # Calculate the distance from the center of the circle to the closest point
25        # of the rectangle along the x-axis.
26        distance_x = distance_to_edge(x1, x2, x_center)
27        # Calculate the distance from the center of the circle to the closest point
28        # of the rectangle along the y-axis.
29        distance_y = distance_to_edge(y1, y2, y_center)
30      
31        # Check if the sum of squares of the distances is less than or equal to
32        # the square of the radius. According to the Pythagorean theorem, this means
33        # the circle overlaps with the rectangle.
34        return distance_x * distance_x + distance_y * distance_y <= radius * radius
35

1class Solution {
2
3    // Method to check if a circle overlaps with an axis-aligned rectangle
4    public boolean checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
5        // Find the shortest distance from the circle's center to the rectangle's border along the x axis
6        int deltaX = shortestDistanceToSegment(x1, x2, xCenter);
7        // Find the shortest distance from the circle's center to the rectangle's border along the y axis
8        int deltaY = shortestDistanceToSegment(y1, y2, yCenter);
9        // Check if the combined distance of both axes' deltas is within the radius (using the Pythagorean theorem)
10        return deltaX * deltaX + deltaY * deltaY <= radius * radius;
11    }
12
13    // Helper method to find the shortest distance from a point 'center' to a line segment defined by 'segmentStart' and 'segmentEnd'
14    private int shortestDistanceToSegment(int segmentStart, int segmentEnd, int center) {
15        // If the center is between the start and end points of the segment, it means the shortest distance is 0
16        if (segmentStart <= center && center <= segmentEnd) {
17            return 0;
18        }
19        // If the center is before the start, calculate the distance from the center to the start
20        if (center < segmentStart) {
21            return segmentStart - center;
22        }
23        // If the center is past the end, calculate the distance from the center to the end
24        return center - segmentEnd;
25    }
26}
27

1class Solution {
2public:
3    // Function to check if the circle with a given radius and center overlaps with a given rectangle.
4    // The rectangle is defined by its bottom-left (x1, y1) and top-right (x2, y2) coordinates.
5    bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
6      
7        // Helper function to calculate the smallest distance from the center of the circle
8        // to the edge of the rectangle along one axis (either x or y).
9        // It takes the minimum and maximum edge coordinate values along one axis
10        // and the center's coordinate along the same axis.
11        auto getMinimumDistance = [](int minEdge, int maxEdge, int centerCoord) -> int {
12            if (centerCoord >= minEdge && centerCoord <= maxEdge) {
13                // The center is inside the rectangle along this axis, so distance is 0.
14                return 0;
15            }
16            // The center is outside the rectangle; calculate the distance to the closer edge.
17            return centerCoord < minEdge ? minEdge - centerCoord : centerCoord - maxEdge;
18        };
19      
20        // Calculate the smallest distances from the circle's center to the rectangle's edges
21        // along the x and y axes.
22        int deltaX = getMinimumDistance(x1, x2, xCenter);
23        int deltaY = getMinimumDistance(y1, y2, yCenter);
24      
25        // Check if the sum of squares of smallest distances is less than or equal to the square of the radius.
26        // If it is, the circle and rectangle overlap.
27        return deltaX * deltaX + deltaY * deltaY <= radius * radius;
28    }
29};
30

1// Function to calculate the minimum distance between a point and a projected point on a line segment
2function calculateMinDistance(lesserCoordinate: number, greaterCoordinate: number, pointCoordinate: number): number {
3    // If the point is between the coordinates, distance is zero (point is within the line segment)
4    if (pointCoordinate >= lesserCoordinate && pointCoordinate <= greaterCoordinate) {
5        return 0;
6    }
7    // If point is before the start of the line segment, return the distance from start
8    if (pointCoordinate < lesserCoordinate) {
9        return lesserCoordinate - pointCoordinate;
10    }
11    // If point is after the end of the line segment, return the distance from the end
12    return pointCoordinate - greaterCoordinate;
13}
14
15// Function to check if a circle overlaps with an axis-aligned rectangle
16function checkOverlap(
17    radius: number,          // Circle's radius
18    circleXCenter: number,   // Circle's X-coordinate center
19    circleYCenter: number,   // Circle's Y-coordinate center
20    rectX1: number,          // Rectangle's top-left X-coordinate
21    rectY1: number,          // Rectangle's top-left Y-coordinate
22    rectX2: number,          // Rectangle's bottom-right X-coordinate
23    rectY2: number           // Rectangle's bottom-right Y-coordinate
24): boolean {
25    // Calculate the distance from the circle's center to the closest point on the X-axis of the rectangle
26    const deltaX = calculateMinDistance(rectX1, rectX2, circleXCenter);
27    // Calculate the distance from the circle's center to the closest point on the Y-axis of the rectangle
28    const deltaY = calculateMinDistance(rectY1, rectY2, circleYCenter);
29    // Check if the square of the distances is less than or equal to the square of the radius
30    // If this condition is true, the circle and rectangle overlap
31    return deltaX * deltaX + deltaY * deltaY <= radius * radius;
32}
33

Not Sure What to Study? Take the 2-min Quiz：

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Time and Space Complexity

Time Complexity: `O(1)`

The checkOverlap function consists of a nested helper f function. The operations inside the f function are simple arithmetic and conditional operations. These operations take constant time. Since there are no loops or recursive calls, the overall time complexity of the function is O(1), which means it executes in constant time regardless of the size of the input parameters.

Space Complexity: `O(1)`

The space complexity is also O(1) because the function only uses a fixed amount of additional space. The helper function f does not utilize additional memory that scales with the input size, and no extra data structures are employed. The variables a and b are the only additional memory used, and their space requirement does not depend on the size of the input.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1401. Circle and Rectangle Overlapping

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

Space Complexity: O(1)

Recommended Readings

Time Complexity: `O(1)`

Space Complexity: `O(1)`