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.In #478 Generate Random Point in a Circle, the goal is to return a point that is uniformly distributed inside a circle with a given radius and center. A naive approach of randomly selecting x and y coordinates inside the bounding square does not guarantee uniform distribution unless we carefully validate whether the point lies inside the circle.
A common strategy is rejection sampling. We repeatedly generate random coordinates inside the square that bounds the circle and accept the point only if it satisfies the circle equation x^2 + y^2 ≤ r^2. This ensures the final distribution is uniform across the circular area.
Another mathematical perspective is to generate a random angle and a radius that accounts for area distribution. Using randomized math transformations ensures that points are not biased toward the center.
Both approaches rely on constant-time random generation. On average, rejection sampling runs in constant expected time, while space usage remains constant since only a few variables are stored.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Rejection Sampling | O(1) average | O(1) |
| Polar Coordinate Randomization | O(1) | O(1) |
nubDotDev
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.
Time Complexity: O(1) on average. Space Complexity: O(1) as no extra space is used.
1#include <random>
2#include <vector>
3#include <cmath>
4
5class Solution {
6 double radius, x_center, y_center;
7 std::default_random_engine generator;
8 std::uniform_real_distribution<double> distribution;
9
10public:
11 Solution(double radius, double x_center, double y_center) : radius(radius), x_center(x_center), y_center(y_center), distribution(-radius, radius) {}
12
13 std::vector<double> randPoint() {
14 double x, y;
15 do {
16 x = distribution(generator);
17 y = distribution(generator);
18 } while (x * x + y * y > radius * radius);
19 return {x_center + x, y_center + y};
20 }
21};This C++ solution mirrors the approach in Python, using the C++ Standard Library’s random utilities to generate points within a bounding square, ensuring uniform distribution inside the circle using rejection sampling.
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.
Time Complexity: O(1). Space Complexity: O(1).
1import java.util.Random;
2
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of problem appears in interviews that test understanding of probability, geometry, and randomized algorithms. It evaluates whether candidates understand uniform sampling and basic mathematical reasoning.
A common optimal approach is rejection sampling. Random points are generated inside the square that bounds the circle and only accepted if they satisfy the circle equation. This guarantees a uniform distribution across the circle with constant expected time.
Rejection sampling ensures that randomly generated points fall strictly inside the circle while maintaining uniform probability. By discarding points outside the circle, we avoid bias introduced by sampling from a square region.
Using polar coordinates is a useful idea. A random angle is chosen uniformly, while the radius is generated using a square root transformation to preserve uniform area distribution inside 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.