How do you solve Generate Random Point in a Circle on LeetCode?

Generate Random Point in a Circle (LeetCode #478) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(1) space complexity. Key insight: Using polar coordinates allows for uniform distribution of points within the circle.

What is the time complexity of Generate Random Point in a Circle?

The optimal solution for Generate Random Point in a Circle runs in O(1) time and uses O(1) space. The time complexity is O(1) because we perform a constant number of operations to generate a random point, regardless of the radius size.

What is the brute force solution for Generate Random Point in a Circle?

The brute force approach for Generate Random Point in a Circle is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we randomly generate points within a bounding box that contains the circle and check if they fall inside the circle. This method is straightforward but inefficient due to the need for repeated checks. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Generate Random Point in a Circle?

Generate Random Point in a Circle uses the following concepts: Math, Geometry, Rejection Sampling, Randomized. The recommended patterns to study are: Randomized Algorithms, Geometric Algorithms.

What are the interview tips for Generate Random Point in a Circle?

Explain your thought process clearly and why you choose a particular approach. Discuss the trade-offs between different methods, especially in terms of efficiency. Practice generating random numbers and understand how to manipulate them for geometric problems.

What are common mistakes when solving Generate Random Point in a Circle?

Not accounting for the edge case where the generated point is on the circumference. Using a fixed bounding box size instead of dynamically adjusting based on the radius.

#478

Generate Random Point in a Circle

Medium

MathGeometryRejection SamplingRandomizedRandomized AlgorithmsGeometric Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(1)	O(1)

💡

Intuition

Time O(1)Space O(1)

This approach uses polar coordinates to generate a random point directly within the circle. By generating a random angle and a random radius, we ensure uniform distribution without the need for rejection sampling.

⚙️

Algorithm

3 steps

1Step 1: Generate a random angle θ between 0 and 2π.
2Step 2: Generate a random radius r such that r² is uniformly distributed between 0 and radius². This can be done by taking the square root of a random number multiplied by radius².
3Step 3: Convert polar coordinates (r, θ) to Cartesian coordinates using x = r * cos(θ) + x_center and y = r * sin(θ) + y_center.

solution.py13 lines

1import random
2import math
3class Solution:
4    def __init__(self, radius: float, x_center: float, y_center: float):
5        self.radius = radius
6        self.x_center = x_center
7        self.y_center = y_center
8    def randPoint(self):
9        theta = random.uniform(0, 2 * math.pi)
10        r = math.sqrt(random.uniform(0, self.radius ** 2))
11        x = r * math.cos(theta) + self.x_center
12        y = r * math.sin(theta) + self.y_center
13        return [x, y]

ℹ

Complexity note: The time complexity is O(1) because we perform a constant number of operations to generate a random point, regardless of the radius size.

1Using polar coordinates allows for uniform distribution of points within the circle.
2Rejection sampling can be inefficient, especially for small circles within larger bounding boxes.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.