LeetCode 478: Generate Random Point in a Circle

Problem Restatement

We are given a circle defined by:

We need to implement a class with two parts:

The returned point must be uniformly distributed inside the circle. A point on the circumference is allowed. The answer is returned as [x, y].

Input and Output

Class shape:

class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        ...

    def randPoint(self) -> list[float]:
        ...

Examples

Example 1:

["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]

The circle has radius 1 and center (0, 0).

Each call to randPoint() returns a random point inside the unit circle.

Possible output:

[None, [-0.72, -0.65], [-0.78, -0.28], [-0.83, -0.19]]

The exact values are random, so many different outputs are valid.

Example 2:

["Solution", "randPoint", "randPoint", "randPoint"]
[[10.0, 5.0, -7.5], [], [], []]

The circle has radius 10 and center (5, -7.5).

Each returned point must lie inside that circle.

First Thought: Pick Random x and y

A simple idea is to pick:

x = random.uniform(x_center - radius, x_center + radius)
y = random.uniform(y_center - radius, y_center + radius)

This picks a point inside the square that surrounds the circle.

But the square contains points outside the circle.

For example, with center (0, 0) and radius 1, the point (1, 1) is inside the square, but outside the circle because:

1^2 + 1^2 = 2 > 1^2

So we must either reject points outside the circle, or generate points directly inside the circle.

Brute Force With Rejection Sampling

The rejection sampling method is simple:

1. Pick a random point inside the bounding square.
2. Check whether it lies inside the circle.
3. If yes, return it.
4. If no, try again.

Code:

import random

class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.radius = radius
        self.x_center = x_center
        self.y_center = y_center

    def randPoint(self) -> list[float]:
        while True:
            x = random.uniform(self.x_center - self.radius, self.x_center + self.radius)
            y = random.uniform(self.y_center - self.radius, self.y_center + self.radius)

            dx = x - self.x_center
            dy = y - self.y_center

            if dx * dx + dy * dy <= self.radius * self.radius:
                return [x, y]

This is correct and often accepted.

The square area is:

(2r) * (2r) = 4r^2

The circle area is:

pi * r^2

So the probability that a random square point lands inside the circle is:

(pi * r^2) / (4r^2) = pi / 4

That is about 0.785.

So the expected number of attempts is about:

4 / pi ≈ 1.27

This is efficient in practice.

Key Insight

We can also generate the point directly using polar coordinates.

A point inside a circle can be described by:

Then the point is:

x = x_center + r * cos(theta)
y = y_center + r * sin(theta)

The angle should be uniform from 0 to 2π.

The radius needs care.

We cannot choose r uniformly from 0 to radius.

That would put too many points near the center. The outer rings have more area than the inner rings, so they should receive more points.

Area grows with the square of the radius:

area = pi * r^2

To make area uniform, choose a random value u from 0 to 1, then use:

r = radius * sqrt(u)

This makes the probability proportional to area, not raw distance.

Algorithm

Store the circle values in the constructor.

For each call to randPoint():

1. Generate a random number u in [0, 1).
2. Set r = radius * sqrt(u).
3. Generate a random angle theta in [0, 2π).
4. Convert from polar coordinates to Cartesian coordinates.
5. Shift the point by the circle center.
6. Return [x, y].

Correctness

The angle theta is chosen uniformly from 0 to 2π, so every direction from the center has equal probability.

The distance r is chosen as:

radius * sqrt(u)

where u is uniform in [0, 1).

For any distance a between 0 and radius, the probability that the generated point lies within distance a of the center is:

P(r <= a)
= P(radius * sqrt(u) <= a)
= P(u <= a^2 / radius^2)
= a^2 / radius^2

That matches the area ratio between the smaller circle of radius a and the full circle:

(pi * a^2) / (pi * radius^2)
= a^2 / radius^2

Therefore, the generated point is uniform by area.

The Cartesian conversion:

x = x_center + r * cos(theta)
y = y_center + r * sin(theta)

places the point exactly at distance r from the center in direction theta.

Since r <= radius, every returned point is inside or on the circle.

Thus the algorithm returns uniformly random valid points inside the circle.

Complexity

Implementation

import math
import random

class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.radius = radius
        self.x_center = x_center
        self.y_center = y_center

    def randPoint(self) -> list[float]:
        u = random.random()
        r = self.radius * math.sqrt(u)

        theta = random.random() * 2 * math.pi

        x = self.x_center + r * math.cos(theta)
        y = self.y_center + r * math.sin(theta)

        return [x, y]

Code Explanation

The constructor stores the circle:

self.radius = radius
self.x_center = x_center
self.y_center = y_center

This line chooses a random area fraction:

u = random.random()

Then we convert that area fraction into a radius:

r = self.radius * math.sqrt(u)

The square root is the important part. Without it, the distribution would cluster near the center.

This line chooses a random direction:

theta = random.random() * 2 * math.pi

Then we convert from polar coordinates to x and y:

x = self.x_center + r * math.cos(theta)
y = self.y_center + r * math.sin(theta)

Finally, return the point:

return [x, y]

Testing

Randomized problems cannot be tested with exact expected output.

Instead, we test properties that every output must satisfy.

def run_tests():
    s = Solution(1.0, 0.0, 0.0)

    for _ in range(10000):
        x, y = s.randPoint()
        assert x * x + y * y <= 1.0 + 1e-12

    s = Solution(10.0, 5.0, -7.5)

    for _ in range(10000):
        x, y = s.randPoint()
        dx = x - 5.0
        dy = y + 7.5
        assert dx * dx + dy * dy <= 100.0 + 1e-12

    print("all tests passed")

run_tests()

Test meaning: