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 <= 1073 * 104 calls will be made to randPoint.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.
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.
Time Complexity: O(1) on average. Space Complexity: O(1) as no extra space is used.
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.
Java
JavaScript
Time Complexity: O(1). Space Complexity: O(1).
Python
| Approach | Complexity |
|---|---|
| Rejection Sampling | Time Complexity: |
| Polar Coordinates | Time Complexity: |
| Default Approach | — |
| 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 |
Leetcode - Generate Random Point in a Circle (Python) • Timothy H Chang • 2,318 views views
Watch 9 more video solutions →Practice Generate Random Point in a Circle with our built-in code editor and test cases.
Practice on FleetCode