algoadvance

Leetcode 478. Generate Random Point in a Circle

Problem Statement

You are asked to implement the Solution class that initializes with the radius and the x-y position of the center of a circle. The class should have a method randPoint that generates a random point within that circle.

Your Solution class should look like this:

class Solution {
public:
    Solution(double radius, double x_center, double y_center);
    vector<double> randPoint();
};

Example:

Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // returns a random point in the circle [0.0,0.0] with radius 1.0

Constraints:

• 0 < radius <= 10^8
• -10^7 <= x_center, y_center <= 10^7
• At most 3 * 10^4 calls will be made to randPoint.

Clarifying Questions

1. How should the random points be distributed?
   • The points should be uniformly distributed within the circle.
2. Is using the standard C++ random library acceptable?
   • Yes, you can use the standard C++ random library for generating random numbers.

Strategy

To generate a random point uniformly in a circle:

1. Polar Coordinates:
   • Generate a random angle θ between 0 and 2π.
   • Generate a random radius r using the inverse transform sampling method where r is adjusted by the square root of a uniform random variable to maintain uniform distribution.
2. Convert to Cartesian Coordinates:
   • Use the formulas:
     • ( x = r \cos(θ) + x_{center} )
     • ( y = r \sin(θ) + y_{center} )

Time Complexity

• Initialization: O(1)
• randPoint(): O(1)

The time complexity for generating a point is constant because it involves basic arithmetic operations and random number generation which are O(1) operations.

Code

Here’s the implementation in C++:

#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>

class Solution {
private:
    double radius, x_center, y_center;

public:
    Solution(double radius, double x_center, double y_center) 
        : radius(radius), x_center(x_center), y_center(y_center) {
        // Initialize random seed
        std::srand(std::time(nullptr));
    }

    std::vector<double> randPoint() {
        double theta = ((double) std::rand() / RAND_MAX) * 2 * M_PI;
        double raw_r = (double) std::rand() / RAND_MAX;
        double r = std::sqrt(raw_r) * radius;
        double x = r * std::cos(theta) + x_center;
        double y = r * std::sin(theta) + y_center;
        return {x, y};
    }
};

Explanation:

• Constructor (Solution): Initializes the circle’s radius and center.
• randPoint Method:
  • Generates a random angle θ between 0 and 2π.
  • Generates a random scaled radius using the square root of a uniform random variable to ensure uniform distribution within the circle.
  • Converts the polar coordinates (r, θ) to Cartesian coordinates (x, y).
  • Adjusts the coordinates by adding the circle’s center coordinates.
  • Returns the computed point as a vector.

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?