478. Generate Random Point in a Circle
Problem Description
Given a circle defined by its radius
and the (x_center, y_center)
coordinates of its center, the task is to create a function randPoint
that can generate a random point within the boundaries of this circle. A valid random point could lie anywhere from the center of the circle to the circumference, with each potential point inside the circle having an equal chance of being selected.
Intuition
The intuitive approach to randomly generating a point within a circle involves two steps - finding a random distance from the center within the range [0, radius] and finding a random angle to pair with this distance.
Here's a breakdown of the solution approach:
-
Generate a random radius: This should be between 0 and the radius of the circle. But we can't simply pick a uniform random number directly between these two because we're working in two dimensions. If we did that, there would be a higher concentration of points near the circumference than near the center — which wouldn't be uniformly random. To get a uniform distribution, we take the square root of a random number between 0 and the square of the radius. In a 2D space, the area of a circle increases with the square of the radius, so this method ensures a uniform distribution of points by their area.
-
Generate a random angle: Angles in a circle range from 0 to 2Ï€ radians, representing 0 to 360 degrees. Each point within the circle corresponds to an angle from the center. By choosing a random angle from this range, we can cover all possible directions uniformly.
-
Calculate the coordinates: With the random length and angle, calculate the x and y coordinates of the random point. We use the random radius (length) to determine how far from the center the point is, and the random angle (degree) to determine the direction. Using the formulas
x = centerX + length * cos(degree)
andy = centerY + length * sin(degree)
, we can find the position of the random point in a Cartesian coordinate system wherecenterX
andcenterY
are the coordinates of the center of the circle.
These steps ensure a uniformly random distribution of generated points within the circle.
Learn more about Math patterns.
Solution Approach
The implementation of the Solution
class in Python takes advantage of the [math](/problems/math-basics)
module for mathematical functions such as math.sqrt
for square root and math.cos
and math.sin
for cosine and sine functions. It also uses random.uniform
to generate a floating-point number within a range. Here is a walk-through of the solution.
-
Class Initialization: The
__init__
method initializes the instance of the class with theradius
,x_center
, andy_center
.1class Solution: 2 def __init__(self, radius: float, x_center: float, y_center: float): 3 self.radius = radius 4 self.x_center = x_center 5 self.y_center = y_center
This is simple setup code that stores the inputs to be used in the
randPoint
method. -
Random Point Generation:
The
randPoint
method is where the random point within the circle is generated.a. Generate a random length from the circle's center by using the square root method described in the intuition section to ensure a uniform distribution.
1 ```python 2 length = [math](/problems/math-basics).sqrt(random.uniform(0, self.radius**2)) 3 ``` 4 5 `random.uniform(0, self.radius**2)` picks a number uniformly between `0` and the square of the `radius`, and then `[math](/problems/math-basics).sqrt` calculates its square root to get a length that has a uniform distribution within the circle when paired with a random angle.
b. Generate a random angle in radians. Any angle for a full rotation around a circle is between
0
and2Ï€
. This is represented by the following line of code:1 ```python 2 degree = random.uniform(0, 1) * 2 * [math](/problems/math-basics).pi 3 ``` 4 5 `random.uniform(0, 1)` generates a number between `0` and `1`, multiplying this by `2 * [math](/problems/math-basics).pi` scales it to the range of `[0, 2Ï€]`.
c. Compute the x and y coordinates based on the random
length
anddegree
. The cosine and sine functions translate the random length and direction into Cartesian coordinates:1 ```python 2 x = self.x_center + length * [math](/problems/math-basics).cos(degree) 3 y = self.y_center + length * math.sin(degree) 4 ``` 5 6 Here, `length * [math](/problems/math-basics).cos(degree)` finds the horizontal distance from the center, and `length * math.sin(degree)` finds the vertical distance from the center. When these are added to `self.x_center` and `self.y_center` respectively, the resulting `(x, y)` is the coordinate of the random point within the circle.
d. Return a list containing the x and y coordinates of the random point:
1 ```python 2 return [x, y] 3 ```
This method can be called multiple times to generate different points within the circle each time it is called.
All of these steps come together to form the randPoint
method of the Solution
class which fulfills the problem requirement of generating a random and uniformly distributed point within a given circle.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we're given a circle with a radius of 5 units and a center at coordinates (2, 3). We want to use the Solution
class to generate a random point within this circle.
First, we initialize the Solution
class with our circle's parameters:
1my_circle = Solution(5, 2, 3)
To generate a random point within the circle defined by my_circle
, we'll walk through the randPoint
method inside the Solution
class.
- Generate a random radius (length):
1length = math.sqrt(random.uniform(0, my_circle.radius**2))
Imagine the random.uniform
function returns 16
after being called with parameters 0
and 25
(since 5 squared is 25
). So math.sqrt(16)
is calculated, resulting in 4
units. This is our random radius, which is uniformly distributed within the circle.
- Generate a random angle (degree):
1degree = random.uniform(0, 1) * 2 * math.pi
Here, random.uniform
returns approximately 0.5
, and when this is multiplied by 2 * math.pi
(approximately 6.283
), we get roughly 3.142
, which is equivalent to 180 degrees in radians. So, our random angle is essentially pointing to the left (west) direction if we imagine the center of the circle corresponding to a compass.
- Calculate the coordinates (x, y):
1x = my_circle.x_center + length * math.cos(degree) 2y = my_circle.y_center + length * math.sin(degree)
With length = 4
and degree ≈ 3.142
, the computations will approximate to:
math.cos(3.142)
≈-1
andmath.sin(3.142)
≈0
.- So,
x ≈ my_circle.x_center + 4 * (-1)
→x ≈ 2 - 4
→x ≈ -2
. y ≈ my_circle.y_center + 4 * 0
→y ≈ 3
.
Thus, the random point's coordinates are approximately (-2, 3)
.
- Return the coordinates:
1return [x, y]
The final result will be a coordinate list [-2, 3]
, which is a random point generated inside our circle of radius 5 with a center at (2, 3).
This example shows how each call to randPoint()
would generate a different random point, uniformly distributed within the circle defined by the radius and center provided to the Solution
class during initialization.
Solution Implementation
1import math
2import random
3from typing import List
4
5class Solution:
6 def __init__(self, radius: float, x_center: float, y_center: float):
7 # Initialize the Solution object with the center coordinates and radius of the circle.
8 self.radius = radius
9 self.x_center = x_center
10 self.y_center = y_center
11
12 def rand_point(self) -> List[float]:
13 # Generate a random length within the range [0, radius] with uniform distribution.
14 # The length is sqrt(R^2 * U) where R is the radius and U is a uniform random number [0,1)
15 length = math.sqrt(random.uniform(0, self.radius**2))
16
17 # Generate a random angle between 0 and 2Ï€ for uniform distribution along the circumference.
18 degree = random.uniform(0, 1) * 2 * math.pi
19
20 # Calculate the x and y coordinates using the length and angle, relative to the center.
21 x = self.x_center + length * math.cos(degree) # Horizontal offset from center.
22 y = self.y_center + length * math.sin(degree) # Vertical offset from center.
23
24 # Return the random point as a list of its x and y coordinates.
25 return [x, y]
26
27# Note: The method name is preserved as 'rand_point' in compliance with the instruction not to modify method names.
28# However, typically in Python, method names would also follow the snake_case convention.
29
1import java.util.Random;
2
3public class Solution {
4 private double radius;
5 private double xCenter;
6 private double yCenter;
7 private Random random;
8
9 public Solution(double radius, double xCenter, double yCenter) {
10 // Initialize the Solution object with the center coordinates and radius of the circle.
11 this.radius = radius;
12 this.xCenter = xCenter;
13 this.yCenter = yCenter;
14 this.random = new Random(); // Initialize the random instance for generating random numbers.
15 }
16
17 public double[] randPoint() {
18 // Generate a random length within the range [0, radius] with uniform distribution.
19 // The length is sqrt(radius^2 * U) where U is a uniform random number in [0, 1).
20 double length = Math.sqrt(this.radius * this.radius * random.nextDouble());
21
22 // Generate a random angle between 0 and 2Ï€ for uniform distribution along the circumference.
23 double angle = random.nextDouble() * 2 * Math.PI;
24
25 // Calculate the x and y coordinates using the length and angle, relative to the center.
26 double x = this.xCenter + length * Math.cos(angle); // Horizontal offset from the center.
27 double y = this.yCenter + length * Math.sin(angle); // Vertical offset from the center.
28
29 // Return the random point as an array of its x and y coordinates.
30 return new double[]{x, y};
31 }
32}
33
1#include <cmath>
2#include <vector>
3#include <random>
4
5class Solution {
6private:
7 double radius;
8 double x_center;
9 double y_center;
10 std::default_random_engine generator;
11 std::uniform_real_distribution<double> distribution;
12
13public:
14 Solution(double radius, double x_center, double y_center)
15 : radius(radius), x_center(x_center), y_center(y_center), distribution(0.0, 1.0) {
16 // Initialize the Solution object with the center coordinates and radius of the circle.
17 }
18
19 std::vector<double> rand_point() {
20 // Generate a random length within the range [0, radius] with uniform distribution.
21 // The length is sqrt(R^2 * U) where R is the radius and U is a uniform random number [0,1)
22 double length = std::sqrt(distribution(generator) * (radius * radius));
23
24 // Generate a random angle between 0 and 2Ï€ for uniform distribution along the circumference.
25 double angle = distribution(generator) * 2 * M_PI;
26
27 // Calculate the x and y coordinates using the length and angle, relative to the center.
28 double x = x_center + length * std::cos(angle); // Horizontal offset from center.
29 double y = y_center + length * std::sin(angle); // Vertical offset from center.
30
31 // Return the random point as a vector of its x and y coordinates.
32 return {x, y};
33 }
34};
35
36// Usage example
37int main() {
38 Solution solution(10.0, 5.0, 5.0);
39 std::vector<double> point = solution.rand_point();
40 // Now `point` contains the random coordinates
41}
42
1import * as math from "mathjs";
2
3// Define the circle's properties globally
4let radius: number;
5let x_center: number;
6let y_center: number;
7
8// Function to initialize the global variables with the center coordinates and radius of the circle
9function initCircle(newRadius: number, newX_center: number, newY_center: number): void {
10 radius = newRadius;
11 x_center = newX_center;
12 y_center = newY_center;
13}
14
15// Function to generate a random point within the circle
16function randPoint(): number[] {
17 // Generate a random length within the range [0, radius] with uniform distribution
18 // The length is the square root of (radius squared multiplied by a uniform random number [0, 1))
19 const length: number = Math.sqrt(Math.random() * (radius ** 2));
20
21 // Generate a random angle between 0 and 2Ï€ for uniform distribution along the circumference
22 const angle: number = Math.random() * 2 * Math.PI;
23
24 // Calculate the x and y coordinates using the length and angle, relative to the center
25 const x: number = x_center + length * Math.cos(angle); // Horizontal offset from center
26 const y: number = y_center + length * Math.sin(angle); // Vertical offset from center
27
28 // Return the random point as an array of its x and y coordinates
29 return [x, y];
30}
31
32// Note: Although we have removed the class definition and included the methods globally,
33// in a typical TypeScript environment, we would still use a class or module to encapsulate these functions.
34// Additionally, 'import * as math from "mathjs";' is used instead of the default 'import math',
35// as TypeScript does not natively have a math module.
36
Time and Space Complexity
Time Complexity
The given code involves calculating a random point within a circle. The randPoint
method contains a constant number of operations regardless of the input size:
random.uniform(0, self.radius**2)
computes a uniform random value between 0 and the square of the radius, which takes constant time O(1).- Taking the square root with
math.sqrt()
is also a constant time operation O(1). random.uniform(0, 1) * 2 * math.pi
computes a random angle, which is again constant time O(1).- The sine and cosine functions are computed once per call to
randPoint
, both of which take constant time O(1). - Multiplying the length and angle calculations to get the
x
andy
coordinates are basic arithmetic operations with constant time O(1).
Since all the operations are executed a constant number of times, the time complexity of the randPoint
method is O(1).
Space Complexity
As for space complexity:
- The
Solution
class holds three variables:self.radius
,self.x_center
, andself.y_center
. This space usage does not scale with the number of timesrandPoint
is called, and they are only stored once when the class instance is created. - Temporary variables used in
randPoint
for length, degree,x
, andy
are re-created on each call and do not accumulate. Thus, the space required for these variables is constant.
Given that no additional space is used that scales with the size of the input or the number of operations, the space complexity of the randPoint
method is O(1).
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.