Generate Random Point in a Circle - Solution & Explanation
Problem Statement
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 circleradiusand 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 * 104calls will be made torandPoint.
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.
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.
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.
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.
Code
Java
JavaScript
Complexity
Time Complexity: O(1). Space Complexity: O(1).
Approach 3: Default Approach
Code
Python
Complexity Comparison
| Approach | Complexity |
|---|---|
| Rejection Sampling | Time Complexity: |
| Polar Coordinates | Time Complexity: |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Rejection Sampling | Expected O(1) | O(1) | When a simple geometric filter is acceptable and implementation simplicity matters |
| Polar Coordinates | O(1) | O(1) | When you want a direct mathematical solution without repeated sampling |
Video Solution
Leetcode - Generate Random Point in a Circle (Python) • Timothy H Chang • 2,345 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Generate Random Point in a Circle easy or hard?
Generate Random Point in a Circle Python/Java solution
How to solve Generate Random Point in a Circle in O(1)?
What is the best approach for Generate Random Point in a Circle?
Is Generate Random Point in a Circle asked at Google/Amazon/Meta?
What data structure is used in Generate Random Point in a Circle?
What is the time complexity of Generate Random Point in a Circle?
Ready to solve this problem?
Practice Generate Random Point in a Circle with our built-in code editor and test cases.
Practice on FleetCode