Abstract / Summary

Check if a circle intersects a rectangle by seeing if the circle's center is inside or near the rectangle or if any rectangle corner is inside the circle.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 50% (50k+ submissions).

Typical patterns to solve this problem:

• Geometry
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The checkOverlap method determines whether a circle and an axis-aligned rectangle intersect. It proceeds through a series of deterministic geometric checks followed by a stochastic sampling phase. Early exit conditions prune impossible cases quickly, while reusable lambda expressions keep the core predicates concise. The random sampling loop adds robustness for configurations that are not captured by the deterministic checks.

Deterministic Bounding-Box Test

The first two if statements compare the rectangle’s extents with the circle’s axis-aligned bounding box. If the rectangle lies completely to the right or above the circle’s bounding box, or completely to the left or below it, the method returns False immediately.

if x1 > xCenter + radius or y1 > yCenter + radius:
    return False
if x2 < xCenter - radius or y2 < yCenter - radius:
    return False

These comparisons eliminate the majority of non-overlapping configurations without any arithmetic beyond simple additions and comparisons.

Predicate Definitions

Two lambda functions encapsulate the core geometric predicates:

insideRect   = lambda x, y: x1 <= x <= x2 and y1 <= y <= y2
insideCircle = lambda x, y: sqrt((x - xCenter)**2 + (y - yCenter)**2) <= radius

insideRect checks whether a point lies within the rectangle’s inclusive bounds, while insideCircle evaluates the Euclidean distance from the circle’s center. Defining them once avoids repeated code and keeps later checks readable.

Direct Intersection Checks

The method then tests several deterministic scenarios that guarantee overlap:

• Circle cardinal points inside the rectangle - the left, right, top, and bottom points on the circle’s perimeter are examined. If any of these lie inside the rectangle, the shapes intersect.

if insideRect(xCenter + radius, yCenter) or insideRect(xCenter - radius, yCenter):
    return True
if insideRect(xCenter, yCenter + radius) or insideRect(xCenter, yCenter - radius):
    return True

• Rectangle corners inside the circle - each of the four rectangle vertices is tested against the circle predicate. A corner inside the circle also confirms overlap.

if insideCircle(x1, y1) or insideCircle(x1, y2) or \
   insideCircle(x2, y1) or insideCircle(x2, y2):
    return True

These checks capture the most common overlap patterns: a circle crossing a rectangle edge or a rectangle corner penetrating the circle.

Stochastic Sampling Phase

When deterministic checks are inconclusive, the method resorts to random sampling. A fixed budget of 1,000 iterations balances thoroughness with runtime predictability.

samples = 1000
for _ in range(samples):
    angle = randint(0, 360) / 180 * pi
    # on the circumference
    x = xCenter + cos(angle) * radius
    y = yCenter + sin(angle) * radius
    if insideRect(x, y):
        return True
    # and inside the circle
    distance = randint(0, radius)
    x = xCenter + cos(angle) * distance
    y = yCenter + sin(angle) * distance
    if insideRect(x, y):
        return True
    # random integer coordinates inside the circle
    x = xCenter + randint(-radius, +radius)
    y = yCenter + randint(-radius, +radius)
    d = sqrt(x*x + y*y)
    if d <= radius and insideRect(x, y):
        return True
    # random integer coordinates inside the rectangle
    x = randint(x1, x2)
    y = randint(y1, y2)
    if insideCircle(x, y):
        return True
    # and on its border
    if insideCircle(x1, y) or insideCircle(x2, y) or \
       insideCircle(x, y1) or insideCircle(x, y2):
       return True

The loop explores several random point families:

• Points on the circle’s perimeter.
• Points uniformly distributed along a radial line inside the circle.
• Integer lattice points within the circle’s axis-aligned bounding square, filtered by the true circular radius.
• Integer lattice points inside the rectangle, tested against the circle.
• Points on the rectangle’s four edges, also tested against the circle.

If any sampled point satisfies the opposite shape’s predicate, the method returns True. After exhausting the sample budget, it concludes that the shapes do not overlap and returns False.

Edge Cases Handled

The early bounding-box test correctly handles cases where the rectangle is completely separated from the circle in any cardinal direction, including when the rectangle touches the circle’s bounding box but does not intersect the actual circle.

The cardinal-point checks treat points exactly on the rectangle’s border as inside because the insideRect predicate uses inclusive comparisons (<=). Similarly, insideCircle includes points on the circle’s circumference due to the <= comparison with the radius.

The corner checks capture scenarios where the rectangle’s vertex lies precisely on the circle’s perimeter.

During random sampling, integer coordinate generation respects the rectangle’s inclusive limits (randint(x1, x2) and randint(y1, y2)), ensuring that border points are considered. The distance check for points generated inside the circle’s square (d <= radius) also includes points on the circle’s edge.

Performance Optimizations

The method’s most significant optimization is the early exit after the bounding-box test, which eliminates the need for any trigonometric or square-root calculations in clearly non-overlapping cases.

Reusing the lambda predicates avoids recomputing the same expressions multiple times, reducing function call overhead and keeping the inner loop tight.

The deterministic checks are placed before the stochastic loop, guaranteeing that the expensive random sampling is only invoked when necessary.

Within the sampling loop, the code reuses the same random angle for both perimeter and interior radial points, saving an extra random number generation per iteration.

Limiting the sampling to a fixed count (1,000) provides a predictable upper bound on execution time, preventing pathological runtimes on pathological geometric configurations.

By generating integer coordinates directly within the rectangle’s bounds, the code avoids unnecessary floating-point arithmetic for those samples, which can be faster on many architectures.

Overall, the combination of early pruning, concise predicate reuse, and a bounded stochastic phase yields a method that quickly resolves the majority of inputs while still offering a probabilistic guarantee for more complex overlap patterns.

Imagine you have a big bouncy ball and a sheet of paper with a square drawn on it. This code tries to figure out if the ball is touching the square at all.

First, the code looks at the cardboard box that perfectly fits the ball. If the square is far away from that box, the ball cannot possibly touch it, so the computer stops early.

Next, the code checks the edges of the ball to see if they land on the square. It also checks the four sharp corners of the square to see if they are hiding inside the ball.

Since fancy shapes can be tricky, the computer then plays a game of throwing a thousand invisible darts. It throws some darts right on the edge of the ball, some inside the ball, and some inside the square. Every time a dart hits both the ball and the paper at the same time, the computer knows the two shapes are touching. If it throws all those darts and none of them manage to connect the two shapes, then the ball and the square are definitely apart.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python	TS
	WalkCCC	C++
	leetcode.ca	C++		Java	Go	Python	TS
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	fsq	C++
	JoshCrozier		JS
	keineahnung2345	C++
	lzl124631x	C++
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lzl124631x	C++
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality