LeetCode Problem 478

Difficulty: 🟡 Medium
Topics: Math, Geometry, Rejection Sampling, Randomized

Solution

LeetCode 478 - Generate Random Point in a Circle

Problem Understanding

This problem asks us to generate random points uniformly inside a circle. The circle is defined by its radius and the coordinates of its center. Every call to randPoint() must return a point [x, y] such that the point lies either inside the circle or exactly on its boundary.

The key requirement is uniform randomness. This means every region of equal area inside the circle must have the same probability of containing a generated point. This requirement is more subtle than it initially appears. A naive implementation can easily introduce bias, even if all generated points technically lie inside the circle.

The input consists of three floating point values:

• radius, the radius of the circle
• x_center, the x-coordinate of the center
• y_center, the y-coordinate of the center

The output of randPoint() is a randomly generated coordinate pair inside the circle.

The constraints are important because they tell us what kind of solution is expected. The radius can be extremely large, up to 10^8, but that does not meaningfully affect complexity because we are not iterating over the area of the circle. The number of calls to randPoint() is at most 3 * 10^4, which means each call should ideally run in constant time.

One of the biggest edge cases is ensuring true uniformity. A common mistake is selecting the radius uniformly from [0, r]. That approach creates a higher density of points near the center because area grows quadratically with radius. Another important consideration is floating point precision, since the output coordinates are floating point values. The problem guarantees valid positive radius values, so we do not need to handle degenerate circles.

Approaches

Brute Force Approach

A straightforward approach is rejection sampling. We generate random points inside the square that bounds the circle, then discard points that fall outside the circle.

The bounding square ranges from:

• x_center - radius to x_center + radius
• y_center - radius to y_center + radius

For every generated point (x, y), we compute:

(x - x_center)^2 + (y - y_center)^2

If this value is less than or equal to radius^2, the point lies inside the circle and we return it. Otherwise, we generate another point.

This approach is correct because the accepted points are uniformly distributed across the circle. However, it is inefficient because many generated points are discarded. The circle occupies only about π/4 ≈ 78.5% of the bounding square, meaning roughly 21.5% of samples are wasted on average.

Optimal Approach

The better solution directly generates points inside the circle using polar coordinates.

A point inside a circle can be represented as:

$x=x_{center}+r\cos(\theta),\quad y=y_{center}+r\sin(\theta)$

The angle θ should be chosen uniformly from [0, 2π).

The crucial insight concerns the radius. If we choose r uniformly from [0, radius], the distribution becomes biased toward the center. This happens because larger radii correspond to larger circular areas.

To achieve uniform area distribution, we instead generate:

$r=R\sqrt{u}$

where:

• R is the circle radius
• u is a uniform random value in [0, 1)

The square root compensates for the quadratic growth of area.

This method generates points directly inside the circle in constant time without rejection.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1) average	O(1)	Uses rejection sampling, wastes samples outside the circle
Optimal	O(1)	O(1)	Directly generates uniformly distributed points using polar coordinates

Algorithm Walkthrough

1. Store the radius and center coordinates in the constructor so they are available for every future call to randPoint().
2. Generate a random angle theta uniformly between 0 and 2π. Every direction from the center must be equally likely.
3. Generate a random value u uniformly between 0 and 1.
4. Compute the actual distance from the center using:

$r=R\sqrt{u}$

This step is essential for achieving uniform area coverage. 5. Convert the polar coordinates into Cartesian coordinates using:

$x=x_{center}+r\cos(\theta),\quad y=y_{center}+r\sin(\theta)$ 6. Return the generated point as [x, y].

Why it works

The algorithm works because the probability density matches the geometry of the circle. The area of a circle with radius r is proportional to r². By generating the radius as sqrt(u) * R, we ensure that the probability of landing within any subregion depends only on its area, not its distance from the center. Since the angle is also uniformly distributed, the final point distribution is uniform across the entire circle.

Python Solution

import math
import random
from typing import List

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]:
        theta = random.uniform(0, 2 * math.pi)

        random_radius = self.radius * math.sqrt(random.random())

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

        return [x, y]

The constructor stores the circle parameters as instance variables so they can be reused efficiently for every random point generation.

Inside randPoint(), the algorithm first generates a random angle between 0 and 2π. This guarantees that all directions are equally likely.

Next, the method computes the radius using sqrt(random.random()). This is the most important part of the solution because it corrects the distribution to account for circular area growth.

Finally, the method converts the polar coordinates into Cartesian coordinates using trigonometric functions and offsets the result by the circle center.

The implementation is compact because the mathematics naturally models the geometry of the problem.

Go Solution

package main

import (
	"math"
	"math/rand"
)

type Solution struct {
	radius  float64
	xCenter float64
	yCenter float64
}

func Constructor(radius float64, x_center float64, y_center float64) Solution {
	return Solution{
		radius:  radius,
		xCenter: x_center,
		yCenter: y_center,
	}
}

func (this *Solution) RandPoint() []float64 {
	theta := rand.Float64() * 2 * math.Pi

	randomRadius := this.radius * math.Sqrt(rand.Float64())

	x := this.xCenter + randomRadius*math.Cos(theta)
	y := this.yCenter + randomRadius*math.Sin(theta)

	return []float64{x, y}
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(radius, x_center, y_center);
 * param_1 := obj.RandPoint();
 */

The Go implementation closely mirrors the Python solution. The struct stores the circle parameters, and RandPoint() generates random polar coordinates before converting them to Cartesian coordinates.

One Go-specific detail is the use of float64 throughout the implementation. Since all geometric calculations involve floating point arithmetic, float64 is the natural choice.

The method returns a slice of float64 values instead of a fixed array because that matches the required LeetCode signature.

Worked Examples

Example 1

Input:

Solution(1.0, 0.0, 0.0)

Suppose the random values generated are:

Variable	Value
theta	1.2
u	0.36

Step 1 computes the adjusted radius:

$r=1.0\times\sqrt{0.36}=0.6$

Step 2 converts to Cartesian coordinates:

Formula	Result
x = 0 + 0.6 × cos(1.2)	0.2174
y = 0 + 0.6 × sin(1.2)	0.5592

Returned point:

[0.2174, 0.5592]

The point lies inside the unit circle because:

$0.2174^2+0.5592^2\approx0.36<1$

Example 2

Input:

Solution(2.0, 3.0, 4.0)

Suppose:

Variable	Value
theta	2.5
u	0.81

Compute radius:

$r=2.0\times\sqrt{0.81}=1.8$

Convert coordinates:

Formula	Result
x = 3 + 1.8 × cos(2.5)	1.558
y = 4 + 1.8 × sin(2.5)	5.077

Returned point:

[1.558, 5.077]

Again, the point is guaranteed to lie inside the circle.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Each call performs a constant number of random generations and arithmetic operations
Space	O(1)	Only a few floating point variables are used

The algorithm runs in constant time because there are no loops or recursive calls. Every invocation of randPoint() performs a fixed sequence of mathematical operations. Space usage is also constant because the implementation stores only the circle parameters and a few temporary variables.

Test Cases

import math

solution = Solution(1.0, 0.0, 0.0)

# Basic validity test, generated point must lie inside unit circle
point = solution.randPoint()
assert point[0] ** 2 + point[1] ** 2 <= 1.0 + 1e-9

# Multiple random points should all lie inside the circle
for _ in range(1000):
    x, y = solution.randPoint()
    assert x * x + y * y <= 1.0 + 1e-9

# Circle with non-zero center
solution2 = Solution(2.0, 3.0, 4.0)

for _ in range(1000):
    x, y = solution2.randPoint()
    dx = x - 3.0
    dy = y - 4.0
    assert dx * dx + dy * dy <= 4.0 + 1e-9

# Very small radius
solution3 = Solution(0.0001, 1.0, 1.0)

for _ in range(100):
    x, y = solution3.randPoint()
    dx = x - 1.0
    dy = y - 1.0
    assert dx * dx + dy * dy <= 0.0001 ** 2 + 1e-12

# Very large radius
solution4 = Solution(1e8, 0.0, 0.0)

for _ in range(100):
    x, y = solution4.randPoint()
    assert x * x + y * y <= (1e8) ** 2 + 1

# Boundary coverage stress test
solution5 = Solution(5.0, -2.0, 7.0)

for _ in range(5000):
    x, y = solution5.randPoint()
    dx = x + 2.0
    dy = y - 7.0
    assert dx * dx + dy * dy <= 25.0 + 1e-9

Test	Why
Unit circle validation	Confirms generated points stay inside the circle
Multiple random samples	Verifies consistency across many calls
Non-zero center	Ensures coordinate translation works correctly
Very small radius	Tests floating point precision handling
Very large radius	Verifies large coordinate arithmetic
Stress test with many samples	Confirms stability under repeated calls

Edge Cases

One important edge case is a very small radius. Floating point precision errors can become noticeable when coordinates are extremely close together. The implementation handles this naturally because all computations use floating point arithmetic consistently, and the distance scaling remains mathematically valid regardless of radius size.

Another important case is a circle whose center is not at the origin. A common mistake is generating points correctly around (0, 0) but forgetting to translate them by the center coordinates. This implementation explicitly adds x_center and y_center after converting polar coordinates into Cartesian coordinates, ensuring correct positioning.

A more subtle edge case involves distribution correctness. If the radius were selected uniformly without the square root transformation, points would cluster near the center. This is one of the most common bugs in solutions to this problem. The implementation avoids this by scaling the radius with sqrt(u), which guarantees uniform area distribution across the circle.