Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
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:
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:
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 <= 104Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
1 0 0 1 -1 3 1
1 1 1 1 -3 2 -1
1 0 0 -1 0 0 1
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1401: Circle and Rectangle Overlapping
class Solution {
public boolean checkOverlap(
int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
int a = f(x1, x2, xCenter);
int b = f(y1, y2, yCenter);
return a * a + b * b <= radius * radius;
}
private int f(int i, int j, int k) {
if (i <= k && k <= j) {
return 0;
}
return k < i ? i - k : k - j;
}
}
// Accepted solution for LeetCode #1401: Circle and Rectangle Overlapping
func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
f := func(i, j, k int) int {
if i <= k && k <= j {
return 0
}
if k < i {
return i - k
}
return k - j
}
a := f(x1, x2, xCenter)
b := f(y1, y2, yCenter)
return a*a+b*b <= radius*radius
}
# Accepted solution for LeetCode #1401: Circle and Rectangle Overlapping
class Solution:
def checkOverlap(
self,
radius: int,
xCenter: int,
yCenter: int,
x1: int,
y1: int,
x2: int,
y2: int,
) -> bool:
def f(i: int, j: int, k: int) -> int:
if i <= k <= j:
return 0
return i - k if k < i else k - j
a = f(x1, x2, xCenter)
b = f(y1, y2, yCenter)
return a * a + b * b <= radius * radius
// Accepted solution for LeetCode #1401: Circle and Rectangle Overlapping
struct Solution;
trait MyClamp {
fn my_clamp(self, min: i32, max: i32) -> i32;
}
impl MyClamp for i32 {
fn my_clamp(self, min: i32, max: i32) -> i32 {
self.max(min).min(max)
}
}
impl Solution {
fn check_overlap(
radius: i32,
x_center: i32,
y_center: i32,
x1: i32,
y1: i32,
x2: i32,
y2: i32,
) -> bool {
let dx = x_center.my_clamp(x1, x2) - x_center;
let dy = y_center.my_clamp(y1, y2) - y_center;
dx * dx + dy * dy <= radius * radius
}
}
#[test]
fn test() {
let radius = 1;
let x_center = 0;
let y_center = 0;
let x1 = 1;
let y1 = -1;
let x2 = 3;
let y2 = 1;
let res = true;
assert_eq!(
Solution::check_overlap(radius, x_center, y_center, x1, y1, x2, y2),
res
);
let radius = 1;
let x_center = 0;
let y_center = 0;
let x1 = -1;
let y1 = 0;
let x2 = 0;
let y2 = 1;
let res = true;
assert_eq!(
Solution::check_overlap(radius, x_center, y_center, x1, y1, x2, y2),
res
);
let radius = 1;
let x_center = 1;
let y_center = 1;
let x1 = -3;
let y1 = -3;
let x2 = 3;
let y2 = 3;
let res = true;
assert_eq!(
Solution::check_overlap(radius, x_center, y_center, x1, y1, x2, y2),
res
);
let radius = 1;
let x_center = 1;
let y_center = 1;
let x1 = 1;
let y1 = -3;
let x2 = 2;
let y2 = -1;
let res = false;
assert_eq!(
Solution::check_overlap(radius, x_center, y_center, x1, y1, x2, y2),
res
);
}
// Accepted solution for LeetCode #1401: Circle and Rectangle Overlapping
function checkOverlap(
radius: number,
xCenter: number,
yCenter: number,
x1: number,
y1: number,
x2: number,
y2: number,
): boolean {
const f = (i: number, j: number, k: number) => {
if (i <= k && k <= j) {
return 0;
}
return k < i ? i - k : k - j;
};
const a = f(x1, x2, xCenter);
const b = f(y1, y2, yCenter);
return a * a + b * b <= radius * radius;
}
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.