478. Generate Random Point in a Circle
Model: qwen3.5:9b
Topics: Math,Random,Rejection Sampling
FAANG asked: 0
Acceptance rate: 39.1%
Problem Breakdown
We are given a circle defined by its radius and the Cartesian coordinates of its center . We need to implement randPoint() which returns [x, y] representing a point uniformly distributed within that circle (including boundary).
Key Constraints & Traps:
- Uniform Distribution: This is the most critical constraint. A “random” point isn’t just picking random and . If we pick points in polar coordinates where both are uniformly distributed linearly (, ), the resulting Cartesian density will be higher near the center than at the edge. This is because area scales with radius squared (). To maintain uniformity over area, we must account for this geometry.
- Input Range: Radius and coordinates can be large, but fit within standard floating-point precision limits (double).
- Performance: We are allowed up to calls. An algorithm with a rejection loop is acceptable ( expected time), but an analytical solution without loops demonstrates better engineering rigor for high-frequency call scenarios.
Intuition
A strong candidate starts by considering the naive approach: pick two random numbers between 0 and radius to form and . This fails immediately because it doesn’t respect circular boundaries or uniform area density.
Next, we consider Rejection Sampling: generate a point in the bounding square around the circle () and check if distance . If not, retry. This works but introduces an expected loop overhead (acceptance rate is ).
The optimal insight comes from probability theory in polar coordinates. The area of a ring at radius with width is proportional to . To have uniform density over the total area, the cumulative distribution function for the radius must be quadratic (). By Inverse Transform Sampling, if we pick a random variable , our distance from center should be . This guarantees uniformity in one pass without rejection loops.
Approach
- Initialize: Store radius and center coordinates as instance variables for reuse across calls.
- Angle Generation: Generate a random angle uniformly between and .
- Radius Calculation:
- Pick a uniform random number
uin range[0, 1]. - Calculate distance from center as
dist = sqrt(u) * radius. This corrects for the area density issue mentioned above.
- Pick a uniform random number
- Cartesian Conversion: Convert polar to Cartesian using and .
- Return: Return the list
[x, y].
Complexity Analysis
- Time Complexity: . We perform a constant number of arithmetic operations (random generation, sqrt, trig functions). There are no loops or retries in this implementation.
- Space Complexity: . We only store the center coordinates and radius as instance variables plus temporary calculation values for each call.
Solution
import math
from typing import List
import random
class Solution:
def __init__(self, radius: float, x_center: float, y_center: float):
self.radius = radius
self.xc = x_center
self.yc = y_center
def randPoint(self) -> List[float]:
# Generate a random angle in radians [0, 2*pi]
theta = random.random() * 2 * math.pi
# To ensure uniform distribution over the area:
# The probability density must be proportional to radius (area element dA ~ r dr).
# Using Inverse Transform Sampling on CDF(r) ~ r^2, we get dist = sqrt(u) * R.
u = random.random()
dist = math.sqrt(u) * self.radius
x = self.xc + dist * math.cos(theta)
y = self.yc + dist * math.sin(theta)
return [x, y]
# Example usage (not part of class definition for LeetCode submission):
# sol = Solution(1.0, 0.0, 0.0)
# print(sol.randPoint())
Edge Cases Handled
- Radius Boundary: The logic holds even if radius is very small or large; floating point precision handles the range without overflow for standard doubles.
- Center Coordinates: Negative coordinates are handled naturally by adding
dist * cos/sinto potentially negativex_center. - Uniformity Guarantee: The use of
sqrt(random())ensures that points near the edge appear as frequently as points near the center, satisfying the problem requirement for a uniform random point.