Domain 2MediumCORE

Generate Random Point in a Circle

We are given a circle defined by its radius and the Cartesian coordinates of its center $(x{center}, y{center})$. We need to implement randPoint() which returns [x, y] representing a point uniformly distributed within that circle (including boundary).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math#Random#Rejection Sampling

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 (xcenter,ycenter)(x_{center}, y_{center}). We need to implement randPoint() which returns [x, y] representing a point uniformly distributed within that circle (including boundary).

Key Constraints & Traps:

  1. Uniform Distribution: This is the most critical constraint. A “random” point isn’t just picking random xx and yy. If we pick points in polar coordinates (r,θ)(r, \theta) where both are uniformly distributed linearly (θ∈[0,2π]\theta \in [0, 2\pi], r∈[0,R]r \in [0, R]), the resulting Cartesian density will be higher near the center than at the edge. This is because area scales with radius squared (A=πr2A = \pi r^2). To maintain uniformity over area, we must account for this geometry.
  2. Input Range: Radius and coordinates can be large, but fit within standard floating-point precision limits (double).
  3. Performance: We are allowed up to 30,00030,000 calls. An algorithm with a rejection loop is acceptable (O(1)O(1) 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 xx and yy. 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 ([xc−r,xc+r]×[yc−r,yc+r][xc-r, xc+r] \times [yc-r, yc+r]) and check if distance ≤r\le r. If not, retry. This works but introduces an expected loop overhead (acceptance rate is π/4\pi/4).

The optimal insight comes from probability theory in polar coordinates. The area of a ring at radius rr with width drdr is proportional to 2πrdr2\pi r dr. To have uniform density over the total area, the cumulative distribution function for the radius must be quadratic (CDF∝r2CDF \propto r^2). By Inverse Transform Sampling, if we pick a random variable u∈[0,1]u \in [0,1], our distance from center should be u×R\sqrt{u} \times R. This guarantees uniformity in one pass without rejection loops.

Approach

  1. Initialize: Store radius and center coordinates as instance variables for reuse across calls.
  2. Angle Generation: Generate a random angle θ\theta uniformly between 00 and 2π2\pi.
  3. Radius Calculation:
    • Pick a uniform random number u in range [0, 1].
    • Calculate distance from center as dist = sqrt(u) * radius. This corrects for the area density issue mentioned above.
  4. Cartesian Conversion: Convert polar (dist,θ)(\text{dist}, \theta) to Cartesian using x=xc+dist⋅cos⁡(θ)x = x_c + dist \cdot \cos(\theta) and y=yc+dist⋅sin⁡(θ)y = y_c + dist \cdot \sin(\theta).
  5. Return: Return the list [x, y].

Complexity Analysis

  • Time Complexity: O(1)O(1). We perform a constant number of arithmetic operations (random generation, sqrt, trig functions). There are no loops or retries in this implementation.
  • Space Complexity: O(1)O(1). 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 [0,108][0, 10^8] without overflow for standard doubles.
  • Center Coordinates: Negative coordinates are handled naturally by adding dist * cos/sin to potentially negative x_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.