Generate Random Point in a Circle

Medium

Generate Random Point in a Circle

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the radius and the coordinates of the circle's center, and what are their possible ranges?
Should the generated point be uniformly distributed within the circle?
Is it acceptable to return a point very close to the edge of the circle, or does it need to be strictly inside (excluding the circumference)?
Should I return the coordinates as integers or floating-point numbers, and what is the required precision?
Can I assume the radius will always be a positive value?

Brute Force Solution

Approach

We need to pick a random spot inside a circle. The brute force way is like throwing darts randomly at a square that covers the whole circle, and then only keeping the darts that landed inside the circle.

Here's how the algorithm would work step-by-step:

Imagine a square that completely covers the circle we're interested in.
Now, randomly pick a point (like throwing a dart) somewhere within that square.
Check if that point is also inside the circle.
If the point is inside the circle, we've found a good random point, and we can stop.
If the point is outside the circle, we ignore it and try again by picking another random point in the square.
Keep repeating this process of picking random points in the square and checking if they are in the circle until we find one that is.

Code Implementation

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 generate(self) -> list[float]:
        while True:
            # Generate random x and y within the square bounds.
            random_x = random.uniform(self.x_center - self.radius, self.x_center + self.radius)
            random_y = random.uniform(self.y_center - self.radius, self.y_center + self.radius)

            # Check if the point is within the circle.
            distance_from_center = math.sqrt((random_x - self.x_center)**2 + (random_y - self.y_center)**2)

            # If the point is inside the circle, return it.
            if distance_from_center <= self.radius:
                return [random_x, random_y]

# Your Solution object will be instantiated and called as such:
# obj = Solution(radius, x_center, y_center)
# param_1 = obj.generate()

Big(O) Analysis

Time Complexity

O(1) – The algorithm generates random points within a square and checks if they fall within a circle. This process repeats until a point inside the circle is found. While the number of iterations is theoretically unbounded, the probability of finding a valid point increases with each iteration. On average, the number of attempts before finding a point inside the circle is constant. Each attempt involves a fixed number of operations (generating random coordinates and checking the distance), therefore the expected time complexity is O(1).

Space Complexity

O(1) – The described solution uses constant auxiliary space. It repeatedly generates random points and checks if they fall within the circle. The only extra memory required is for storing a few variables such as the x and y coordinates of the random point and potentially a boolean flag to indicate if the point is within the circle. The number of variables does not depend on any input size N, so the space used is constant.

Optimal Solution

Approach

The challenge is to pick random spots inside a circle fairly. The tricky part is realizing that if you pick the radius and angle separately and uniformly, you'll end up with points clustered towards the center. Instead, we need to pick the square of the radius to ensure an even spread.

Here's how the algorithm would work step-by-step:

First, pick a random value that represents the square of the distance from the center of the circle to the random point.
Then, find the actual distance by taking the square root of this value.
Next, choose a random angle between 0 and 360 degrees (or 0 and 2 times pi radians) which will give us the direction of our point.
Now, using this distance and angle, calculate the x and y coordinates of our random point relative to the center of the circle using basic trigonometry (sine and cosine).
Finally, if the circle isn't centered at the origin, shift the calculated x and y coordinates by adding the coordinates of the circle's center.

Code Implementation

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):
        # Generate the square of the radius for uniform sampling
        squared_radius = random.random() * (self.radius ** 2)

        # Calculate the actual radius
        distance_from_center = math.sqrt(squared_radius)

        # Generate a random angle
        random_angle = random.random() * 2 * math.pi

        # Calculate the x and y coordinates
        x_coordinate = self.x_center + distance_from_center * math.cos(random_angle)
        y_coordinate = self.y_center + distance_from_center * math.sin(random_angle)
        
        return [x_coordinate, y_coordinate]

Big(O) Analysis

Time Complexity

O(1) – The algorithm involves a fixed number of operations regardless of any input size. It generates a random value, calculates a square root, generates another random value, performs trigonometric calculations (sine and cosine), and adds constants. All these operations take constant time, therefore the time complexity is O(1).

Space Complexity

O(1) – The algorithm uses a few constant space variables to store the squared radius, actual radius, angle, x coordinate, and y coordinate. These variables consume a fixed amount of memory regardless of the circle's radius or center coordinates, which represent the input. There are no auxiliary data structures created that depend on the input size. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Radius is zero	Return the center point (x, y) since that's the only valid point
Radius is negative	Throw an IllegalArgumentException as radius should be non-negative
Very large radius (close to the maximum floating-point value)	Ensure intermediate calculations (e.g., radius * random number) do not overflow or lose significant precision
Center coordinates are extremely large or small	Ensure offsets from the center don't cause overflow or underflow problems during coordinate generation
Floating-point precision errors causing infinite loop near the edge	Use Math.random() * radius carefully to avoid potential infinite loops from floating point comparison issues.
Generating many points repeatedly	Ensure randomness of points does not degrade over many iterations
Center point is at the origin (0, 0)	The algorithm handles the origin without modification as it functions the same mathematically.
X and Y coordinates could have different scales (e.g., very large X and small Y)	The standard algorithm works as it is normalized to the radius.