algoadvance

Leetcode 478. Generate Random Point in a Circle

Problem Statement

You have a circle with a radius radius and a center at the origin (0, 0). 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 and y_center.
• double[] 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:

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

Explanation:
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return a random point in the circle
solution.randPoint(); // return a random point in the circle
solution.randPoint(); // return a random point in the circle

Clarifying Questions

1. Is the center always at the origin? No, the center can be anywhere, but typically it may often start at the origin for simplicity.
2. Are there any constraints on the radius? Radius is always positive.
3. Is there a requirement for the distribution to be uniform? Yes, the point generation inside the circle should be uniform.

Strategy

1. Random Point Generation Approach:
   • To uniformly distribute the points inside a circle, we use polar coordinates where we randomly generate the angle theta and radius r.
   • Angle theta can be uniformly selected from [0, 2*pi).
   • Radius r needs to be scaled correctly to ensure uniform distribution; hence, we use a random number in [0, 1] and take its square root to avoid clustering towards the center.
2. Converting Polar to Cartesian Coordinates:
   • Convert the generated polar coordinates (r, theta) to Cartesian coordinates (x, y) using the formula:
     • ( x = r \cdot \cos(\theta) )
     • ( y = r \cdot \sin(\theta) )
3. Adjust for Circle’s Center:
   • Offset the generated (x, y) by the circle’s center (x_center, y_center).

Code

import java.util.Random;

public 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 theta = 2 * Math.PI * rand.nextDouble();
        double r = Math.sqrt(rand.nextDouble()) * radius;
        double x = r * Math.cos(theta) + x_center;
        double y = r * Math.sin(theta) + y_center;
        return new double[] {x, y};
    }
}

Time Complexity

• Initialization (Solution Constructor): O(1)
• Generating a Random Point (randPoint Method): O(1)

Explanation:

• The constructor simply initializes the class variables which is done in constant time.
• The randPoint method involves generating random numbers, calculating trigonometric functions, and performing arithmetic operations, all of which are constant time operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?