1401 LeetCode problem solution

LeetCode problem link: 1401. Circle and Rectangle Overlapping


LeetCode 1401 problem description

Medium level problem.


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.


Example 1: leetcode 1401 Circle and Rectangle Overlapping example image

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0).


Example 2:


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


Example 3: leetcode 1401 Circle and Rectangle Overlapping example image

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true


Constraints:

  • 1 <= radius <= 2000
  • -104 <= xCenter, yCenter <= 104
  • -104 <= x1 < x2 <= 104
  • -104 <= y1 < y2 <= 104

LeetCode 1401. Circle and Rectangle Overlapping solution

The circle and rectangle overlap if the distance from the circle's center to the closest point inside the rectangle is less than or equal to the circle's radius.

Find the closest point (closestX, closestY) by clamping the circle center coordinates to the rectangle boundaries:

closestX = max(x1, min(xCenter, x2))
closestY = max(y1, min(yCenter, y2))

Then calculate the squared distance from the circle center to this point:

dx = xCenter - closestX
dy = yCenter - closestY
distanceSquared = dx * dx + dy * dy

The circle and rectangle overlap when:

distanceSquared <= radius * radius

Using squared distance avoids the unnecessary square root operation.


LeetCode 1401. Circle and Rectangle Overlapping example

radius = 1
xCenter = 0
yCenter = 0

rectangle:
x1 = 1
y1 = -1
x2 = 3
y2 = 1

The closest point in the rectangle to the circle center (0, 0) is (1, 0):

closestX = max(1, min(0, 3)) = 1
closestY = max(-1, min(0, 1)) = 0

Now calculate the squared distance:

dx = 0 - 1 = -1
dy = 0 - 0 = 0

distanceSquared = (-1)^2 + 0^2 = 1
radius^2 = 1

Since:

1 <= 1

the circle touches the rectangle, so the answer is true.


Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

LeetCode 1401 C++ solution

class Solution {
public:
  bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
    int closestX = max(x1, min(xCenter, x2));
    int closestY = max(y1, min(yCenter, y2));

    int dx = xCenter - closestX;
    int dy = yCenter - closestY;

    return dx * dx + dy * dy <= radius * radius;
  }
};

LeetCode 1401 Java solution

class Solution {
  public boolean checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
    int closestX = Math.max(x1, Math.min(xCenter, x2));
    int closestY = Math.max(y1, Math.min(yCenter, y2));

    int dx = xCenter - closestX;
    int dy = yCenter - closestY;

    return dx * dx + dy * dy <= radius * radius;
  }
}

LeetCode 1401 JavaScript solution

var checkOverlap = function(radius, xCenter, yCenter, x1, y1, x2,y2) {
  const closestX = Math.max(x1, Math.min(xCenter, x2));
  const closestY = Math.max(y1, Math.min(yCenter, y2));

  const dx = xCenter - closestX;
  const dy = yCenter - closestY;

  return dx * dx + dy * dy <= radius * radius;
};

LeetCode 1401 TypeScript solution

function checkOverlap(radius: number, xCenter: number, yCenter: number, x1: number, y1: number, x2: number,y2: number): boolean {
  const closestX = Math.max(x1, Math.min(xCenter, x2));
  const closestY = Math.max(y1, Math.min(yCenter, y2));

  const dx = xCenter - closestX;
  const dy = yCenter - closestY;

  return dx * dx + dy * dy <= radius * radius;
}

LeetCode 1401 Python solution

class Solution:
  def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
    closestX = max(x1, min(xCenter, x2))
    closestY = max(y1, min(yCenter, y2))

    dx = xCenter - closestX
    dy = yCenter - closestY

    return dx * dx + dy * dy <= radius * radius