Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Generate Random Point in a Circle solution and explanation

MediumGeometryMathRandomizedRejection Sampling5 min read43.8% acceptanceUpdated 9 Apr 2026
Asked atLeap MotionMeta
Practise Generate Random Point in a Circle
4:21
Leetcode - Generate Random Point in a Circle (Python)Timothy H Chang · 4:21 · 2K viewsWatch on YouTube
9 more videos on this problem
  1. Leetcode - Generate Random Point in a Circle (Python)Timothy H Chang · 4:21 · 2K views
  2. Generate Random Point in a Circle | Leetcode 478Coding Decoded · 10:59 · 2K views
  3. #Leetcode #478. Generate Random Point in a Circle #random generatorCode with Alisha · 15:40 · 2K views
  4. Leetcode[478] Generate random points in a circle ..shyam tripathy · 8:42 · 736 views
  5. LeetCode 478 - Generate Random Point In CircleLight Of Truth · 7:45 · 430 views
  6. Generate Random Point in a Circle | LeetCode 478 | Coders CampCoders Camp · 7:41 · 342 views
  7. LeetCode 478. Generate Random Point in a Circle | PythonLea's coding · 4:19 · 154 views
  8. Generate Random Point in a Circle | LeetCode 478The Code Architect · 12:59 · 115 views
  9. March 2021 Day 17 LeetCode challenge | 478. Generate Random Point in a CircleAnushka Bhagchandani · 9:42 · 40 views
  10. How to begin solving medium tier Leetcode problems: Problem 478: Generating Random Point in a CirclePewaukee · 24:48 · 13 views

The problem

Given the radius and the position of the center of a circle, implement the function randPoint which generates a uniform random point inside the circle.

Implement the Solution class:

  • Solution(double radius, double x_center, double y_center) initializes the object with the radius of the circle radius and the position of the center (x_center, y_center).
  • randPoint() returns a random point inside the circle. A point on the circumference of the circle is considered to be in the circle. The answer is returned as an array [x, y].

Example 1:

Input
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
Output
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return [-0.02493, -0.38077]
solution.randPoint(); // return [0.82314, 0.38945]
solution.randPoint(); // return [0.36572, 0.17248]

Constraints:

  • 0 < radius <= 108
  • -107 <= x_center, y_center <= 107
  • At most 3 * 104 calls will be made to randPoint.

Approach overview

Problem Overview: You need to generate a random point uniformly distributed inside a circle defined by radius and center (x_center, y_center). The key challenge is ensuring every location inside the circle has equal probability, not just points near the center.

Approach 1: Rejection Sampling (Expected O(1) time, O(1) space)

This approach samples points from the bounding square around the circle. Generate random x and y offsets uniformly in the range [-radius, radius]. If the sampled point satisfies x^2 + y^2 <= radius^2, it lies inside the circle and is accepted. Otherwise discard it and sample again. The acceptance probability is roughly π/4 ≈ 0.785, so the expected number of iterations is constant.

The key insight is that uniform sampling from the square combined with a geometric filter preserves uniform distribution inside the circle. The algorithm repeatedly performs random generation and a simple distance check. This technique is widely used in rejection sampling problems where generating a direct distribution is difficult.

Approach 2: Polar Coordinates (O(1) time, O(1) space)

A more mathematically direct method uses polar coordinates. Generate a random angle θ uniformly in [0, 2π]. For the radius, generate a random value r = sqrt(U) * radius where U is uniform in [0,1]. The square root is crucial because area grows with r², so naive uniform sampling of r would cluster points near the center.

Convert the polar coordinate to Cartesian form using x = x_center + r * cos(θ) and y = y_center + r * sin(θ). This guarantees uniform distribution across the entire circle in a single step. The approach relies on geometric reasoning and is common in problems involving math and geometry.

Recommended for interviews: Both approaches are acceptable. Rejection sampling is easy to derive and demonstrates understanding of geometric filtering. The polar coordinate method is more elegant and avoids repeated sampling, which often impresses interviewers because it shows deeper mathematical reasoning about uniform distributions.

Approach 1: Rejection Sampling

Rejection sampling is a technique used to generate samples from a distribution by generating samples from a proposal distribution and then rejecting some of the samples. In the context of this problem, you can generate random points in a square that circumscribes the circle and then only accept those points that lie inside the circle.

import random
import math

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.radius, self.radius)
            y = random.uniform(-self.radius, self.radius)
            if x * x + y * y <= self.radius * self.radius:
                return [self.x_center + x, self.y_center + y]
#include <random>
#include <vector>
#include <cmath>

class Solution {
    double radius, x_center, y_center;
    std::default_random_engine generator;
    std::uniform_real_distribution<double> distribution;

public:
    Solution(double radius, double x_center, double y_center) : radius(radius), x_center(x_center), y_center(y_center), distribution(-radius, radius) {}

    std::vector<double> randPoint() {
        double x, y;
        do {
            x = distribution(generator);
            y = distribution(generator);
        } while (x * x + y * y > radius * radius);
        return {x_center + x, y_center + y};
    }
};

This solution uses a square of side double the radius centered at the (x_center, y_center) to generate random points. If the point lies within the circle (determined by the condition x^2 + y^2 <= radius^2), it is returned, otherwise the process is repeated.

Complexity

Time Complexity: O(1) on average. Space Complexity: O(1) as no extra space is used.

Try this approach in the editor

Approach 2: Polar Coordinates

Instead of generating points in a square and rejecting those outside the circle, we can directly generate points within the circle using polar coordinates. By randomly selecting an angle and a distance from the center, and then converting these polar coordinates to Cartesian coordinates, we can efficiently generate a uniform random point within the circle.

import java.util.Random;

class Solution {
    private double radius;
    private double x_center;
    private double y_center;
    private Random rand;

    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.x_center = x_center;
        this.y_center = y_center;
        this.rand = new Random();
    }

    public double[] randPoint() {
        double angle = rand.nextDouble() * 2 * Math.PI;
        double radius = Math.sqrt(rand.nextDouble()) * this.radius;
        double x = x_center + radius * Math.cos(angle);
        double y = y_center + radius * Math.sin(angle);
        return new double[]{x, y};
    }
}
class Solution {
    constructor(radius, x_center, y_center) {
        this.radius = radius;
        this.x_center = x_center;
        this.y_center = y_center;
    }

    randPoint() {
        let angle = Math.random() * 2 * Math.PI;
        let radius = Math.sqrt(Math.random()) * this.radius;
        let x = this.x_center + radius * Math.cos(angle);
        let y = this.y_center + radius * Math.sin(angle);
        return [x, y];
    }
}

This Java solution utilizes polar coordinates to generate a point by first determining a random angle and a random radial distance (scaled correctly) within the circle. The radial distance is the square root of a random number between 0 and 1 multiplied by the circle's radius to ensure uniform distribution.

Complexity

Time Complexity: O(1). Space Complexity: O(1).

Try this approach in the editor

Complexity comparison

ApproachComplexity
Rejection Sampling

Time Complexity: O(1) on average. Space Complexity: O(1) as no extra space is used.

Polar Coordinates

Time Complexity: O(1). Space Complexity: O(1).

Complexity analysis

ApproachTimeSpaceWhen to Use
Rejection SamplingExpected O(1)O(1)When a simple geometric filter is acceptable and implementation simplicity matters
Polar CoordinatesO(1)O(1)When you want a direct mathematical solution without repeated sampling

Frequently asked questions

Is Generate Random Point in a Circle easy or hard?

The problem is rated Medium because the challenge is understanding uniform distribution over an area. Generating random x and y independently leads to incorrect distributions. The correct approach requires either rejection sampling or adjusting the radius with a square root transformation.

Generate Random Point in a Circle Python/Java solution

Python solutions typically use rejection sampling with random.uniform or the polar coordinate formula with math.sqrt, math.cos, and math.sin. Java implementations commonly use the polar coordinate approach with Math.random() and trigonometric functions to generate the final (x, y) coordinates.

How to solve Generate Random Point in a Circle in O(1)?

Use polar coordinates. Generate a random angle θ in [0, 2π] and a random value U in [0,1]. Compute the radius as r = sqrt(U) * radius to maintain uniform area distribution, then convert to Cartesian coordinates using x = x_center + r*cos(θ) and y = y_center + r*sin(θ). This produces a uniform point in constant time.

What is the best approach for Generate Random Point in a Circle?

Two common solutions are rejection sampling and polar coordinates. Rejection sampling randomly generates points inside the bounding square and accepts those inside the circle with expected O(1) time. The polar coordinate approach is often considered the optimal mathematical solution because it directly produces a uniformly distributed point in a single computation.

Is Generate Random Point in a Circle asked at Google/Amazon/Meta?

This problem appears in interviews at companies that emphasize probability, geometry, and randomized algorithms. Variations of random sampling and geometric probability have been reported in interviews at Google, Amazon, and other large tech companies.

What data structure is used in Generate Random Point in a Circle?

The problem does not rely on complex data structures. It primarily uses random number generation and mathematical computations. The main concepts come from geometry, probability distributions, and randomized algorithms.

What is the time complexity of Generate Random Point in a Circle?

Both main approaches run in constant time. Rejection sampling has expected O(1) time because about 78.5% of generated points fall inside the circle. The polar coordinate method also runs in O(1) time since it performs a fixed number of random generations and mathematical operations.

Comments

Next problem · similarRandom Point in Non-overlapping RectanglesMedium
Now write it yourselfClose this page and solve Generate Random Point in a Circle in the editor, without looking.
Practise Generate Random Point in a Circle