algoadvance

Leetcode 497. Random Point in Non

Problem Statement

Given an array of non-overlapping axis-aligned rectangles rects where rects[i] = [ai, bi, xi, yi] represents the rectangle with lower left corner (ai, bi) and upper right corner (xi, yi). Implement the function pick() to randomly select a point within one of these rectangles with a uniform probability. The rectangles are non-overlapping, so any given point in the space falls into at most one rectangle.

Implement the Solution class:

Clarifying Questions

  1. Are the coordinates of the rectangles integers?
    • Yes, the coordinates of the rectangles are given as integers.
  2. What is the range of coordinates and the number of rectangles?
    • The coordinates and the number of rectangles are within reasonable bounds as per typical coding challenges, but specifics can be found in the problem if additional constraints are noted.
  3. Is the distribution strictly uniform over the area covered by all rectangles?
    • Yes, each point in the area covered by the rectangles should have an equal probability of being picked.

Strategy

  1. Compute the Total Number of Points:
    • For each rectangle, calculate the number of points it contains.
    • Maintain a cumulative count of points.
  2. Random Point Selection:
    • Generate a random number within the total number of points.
    • Determine which rectangle this point falls into based on cumulative sums.
  3. Point Generation within Rectangle:
    • For the selected rectangle, compute the exact coordinates for the point.

Code

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

class Solution {
    vector<vector<int>> rects;
    vector<int> prefixSums;
    int totalPoints;

public:
    Solution(vector<vector<int>>& rects) : rects(rects), totalPoints(0) {
        srand(time(0));  // Seed for random number generation
        
        for (auto& rect : rects) {
            // Calculate the number of points in the current rectangle
            int numPoints = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            totalPoints += numPoints;
            prefixSums.push_back(totalPoints);
        }
    }

    vector<int> pick() {
        // Generate a random number in range [1, totalPoints]
        int randPoint = rand() % totalPoints + 1;
        
        // Binary search to find the rectangle containing the randPoint
        int lo = 0, hi = rects.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (prefixSums[mid] < randPoint) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        // lo now is the index of the target rectangle
        vector<int>& selectedRect = rects[lo];
        
        // Calculate the offset within the selected rectangle
        int pointsInPreviousRects = (lo == 0) ? 0 : prefixSums[lo - 1];
        int offset = randPoint - pointsInPreviousRects - 1;

        int width = selectedRect[2] - selectedRect[0] + 1;
        int x = selectedRect[0] + (offset % width);
        int y = selectedRect[1] + (offset / width);
        
        return {x, y};
    }
};

int main() {
    vector<vector<int>> rects = \{\{1, 1, 5, 5}, {10, 10, 13, 13}, {20, 20, 25, 25}};
    Solution solution(rects);
    for (int i = 0; i < 10; ++i) {
        vector<int> point = solution.pick();
        cout << "Random Point: (" << point[0] << ", " << point[1] << ")\n";
    }
    return 0;
}

Time Complexity

This approach ensures efficient point selection with uniform distribution.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI