LeetCode 478: Generate Random Point in a Circle Solution in Python – A Step-by-Step Guide

What Is LeetCode 478: Generate Random Point in a Circle?

In LeetCode 478: Generate Random Point in a Circle, you’re tasked with implementing a class that generates uniform random points inside a circle defined by a radius radius and center (x_center, y_center). The class has a method randPoint() that returns a list [x, y] representing a point’s coordinates within the circle, ensuring every point has an equal chance of being selected. For example, with radius = 1 and center = (0, 0), points like [0.5, 0.3] or [-0.2, 0.9] should be equally likely. It’s like scattering seeds evenly across a circular garden patch.

Problem Statement

• Input:
• Solution(radius: float, x_center: float, y_center: float)—initialize with radius and center.
• randPoint()—generate a random point.
• Output: List[float]—[x, y] coordinates inside the circle.
• Rules:
• Point must be within or on the circle (distance ≤ radius).
• Distribution must be uniform (equal probability per area).
• Use random.random() for randomness (0 to 1).

Constraints

• 10^-5 <= radius <= 10^4.
• -10^4 <= x_center, y_center <= 10^4.
• At most 3 * 10^4 calls to randPoint().

Examples to Get Us Started

• Input: ["Solution","randPoint","randPoint","randPoint"], [[1.0,0.0,0.0],[],[],[]]
• Output: [null,[0.5,-0.3],[-0.2,0.8],[0.1,0.9]] (Random points within radius 1).
• Input: ["Solution","randPoint"], [[2.0,1.0,1.0],[]]
• Output: [null,[1.2,2.1]] (Point within radius 2 from (1,1)).

Understanding the Problem: Scattering the Darts

To solve LeetCode 478: Generate Random Point in a Circle in Python, we need to generate x, y coordinates within a circle of radius r centered at (x_center, y_center) such that every point has an equal probability per unit area. A naive approach—generating random x and y within a square and rejecting points outside the circle—works but needs optimization. The key? Use rejection sampling or polar coordinates to ensure uniformity. We’ll explore:

• Best Solution (Rejection Sampling with Square-to-Circle Mapping): O(1) expected time, O(1) space—fast and intuitive.
• Alternative Solution (Polar Coordinate Method): O(1) time, O(1) space—precise but complex.

Let’s dive into the rejection sampling solution—it’s the dart player’s quick aim we need.

Best Solution: Rejection Sampling with Square-to-Circle Mapping

Why This Is the Best Solution

The rejection sampling with square-to-circle mapping is the top pick because it’s O(1) expected time and O(1) space, generating uniform points by sampling within a bounding square and rejecting those outside the circle, with a simple and intuitive implementation. It leverages Python’s random.random() for speed and clarity, avoiding complex math while ensuring uniformity. It’s like throwing darts at a square board and keeping only those that hit the circular target—straightforward and efficient!

How It Works

Here’s the strategy:

• Step 1: Define a bounding square around the circle:
• Side length = 2 * radius.
• Center at (x_center, y_center).
• Range: x from x_center - radius to x_center + radius, y similar.
• Step 2: Generate random x, y within the square:
• x = x_center + (random.random() * 2 - 1) * radius.
• y = y_center + (random.random() * 2 - 1) * radius.
• Step 3: Rejection sampling:
• Check if (x, y) is within circle: (x - x_center)² + (y - y_center)² ≤ radius².
• If outside, retry.
• Step 4: Return [x, y].
• Why It Works:
• Square encloses circle, uniform sampling in square.
• Rejection ensures only circle points remain, uniform due to symmetry.

Step-by-Step Example

Example: radius = 1.0, x_center = 0.0, y_center = 0.0

• Bounding Square: [-1, 1] x [-1, 1].
• Trial 1:
• x = 0 + (0.7 * 2 - 1) * 1 = 0.4.
• y = 0 + (0.9 * 2 - 1) * 1 = 0.8.
• Dist² = 0.4² + 0.8² = 0.16 + 0.64 = 0.8 ≤ 1, accept.
• Result: [0.4, 0.8].
• Trial 2:
• x = 0.9, y = 0.9, Dist² = 1.62 > 1, reject, retry.

Example: radius = 2.0, x_center = 1.0, y_center = 1.0

• Square: [-1, 3] x [-1, 3].
• Trial: x = 1 + (0.3 * 4 - 2) = 0.2, y = 1.8, Dist² = 0.68 ≤ 4, accept.
• Result: [0.2, 1.8].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeimport random

class Solution:
    def __init__(self, radius: float, x_center: float, y_center: float):
        # Step 1: Store circle parameters
        self.radius = radius
        self.x_center = x_center
        self.y_center = y_center

    def randPoint(self) -> List[float]:
        while True:
            # Step 2: Generate random x, y in bounding square
            x = self.x_center + (random.random() * 2 - 1) * self.radius
            y = self.y_center + (random.random() * 2 - 1) * self.radius

            # Step 3: Check if within circle
            dist_squared = (x - self.x_center) ** 2 + (y - self.y_center) ** 2
            if dist_squared <= self.radius ** 2:
                # Step 4: Return point
                return [x, y]
            # Else retry

• Line 6-8: Store radius and center in constructor.
• Line 11-12: Generate x, y in square:
• random.random() * 2 - 1 gives -1 to 1, scaled by radius.
• Line 15-18: Check distance² ≤ radius², return if inside, retry if outside.
• Time Complexity: O(1) expected—rejection rate π/4 (~0.785), avg ~1.27 tries.
• Space Complexity: O(1)—few variables.

It’s like a dart-throwing ace!

Alternative Solution: Polar Coordinate Method

Why an Alternative Approach?

The polar coordinate method—O(1) time, O(1) space—generates points using radius and angle (r, θ), ensuring uniformity by sampling r proportional to sqrt(random()) and θ from 0 to 2π. It’s precise but requires math, like plotting a dart’s landing with a compass and protractor. Good for mathematical elegance or avoiding rejection!

How It Works

• Step 1: Generate random radius r:
• r = radius * sqrt(random()) (uniform area distribution).
• Step 2: Generate random angle θ:
• θ = 2 * π * random().
• Step 3: Convert to Cartesian:
• x = x_center + r * cos(θ).
• y = y_center + r * sin(θ).
• Step 4: Return [x, y].
• Why It Works:
• sqrt(r) adjusts for area (πr²), ensuring uniformity.
• θ spans full circle evenly.

Step-by-Step Example

Example: radius = 1.0, x_center = 0.0, y_center = 0.0

• r: sqrt(0.25) = 0.5.
• θ: 2 * π * 0.5 = π.
• x: 0 + 0.5 * cos(π) = -0.5.
• y: 0 + 0.5 * sin(π) = 0.
• Result: [-0.5, 0].

Code for Polar Coordinates

Copy codeimport 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) -> List[float]:
        # Step 1: Random radius with sqrt for uniformity
        r = self.radius * math.sqrt(random.random())

        # Step 2: Random angle
        theta = 2 * math.pi * random.random()

        # Step 3: Convert to Cartesian
        x = self.x_center + r * math.cos(theta)
        y = self.y_center + r * math.sin(theta)

        # Step 4: Return point
        return [x, y]

• Line 11: r = radius * sqrt(random()) for area uniformity.
• Line 14: θ = 2π * random() for full circle.
• Line 17-18: Compute x, y using polar to Cartesian.
• Time Complexity: O(1)—no rejection, direct calc.
• Space Complexity: O(1)—minimal space.

It’s a compass-guided dart!

Comparing the Two Solutions

• Rejection Sampling (Best):
• Pros: O(1) expected, simple, intuitive.
• Cons: ~1.27 calls avg (π/4 rejection).
• Polar Coordinates (Alternative):
• Pros: O(1), no rejection, precise.
• Cons: Math-heavy (sin, cos, sqrt).

Rejection sampling wins for simplicity.

Edge Cases and Examples

• Radius = 0: Points at center.
• Large Radius: Uniform spread.
• Offset Center: Correct shift.

Rejection sampling handles all well.

Complexity Recap

• Rejection Sampling: Expected Time O(1) (~1.27 calls), Space O(1).
• Polar Coordinates: Time O(1), Space O(1).

Rejection sampling’s the champ for ease.

Key Takeaways

• Rejection Sampling: Throw and check.
• Polar Coordinates: Plot with math.
• Python Tip: Random rocks—see [Python Basics](/python/basics).

Final Thoughts: Hit That Target

LeetCode 478: Generate Random Point in a Circle in Python is a dart-throwing geometry adventure. Rejection sampling is your quick aim, while polar coordinates are a precise shot. Want more randomness? Try LeetCode 470: Implement Rand10() Using Rand7() or LeetCode 384: Shuffle an Array. Ready to scatter some points? Head to Solve LeetCode 478 on LeetCode and throw it today—your coding skills are target-ready!