Random Point in Non-overlapping Rectangles

Random Point in Non-overlapping Rectangles - Problem

Array Math Binary Search Reservoir Sampling Prefix Sum Ordered Set Randomized Medium

You are given an array of non-overlapping axis-aligned rectangles rects where rects[i] = [ai, bi, xi, yi] indicates that (ai, bi) is the bottom-left corner point of the i^th rectangle and (xi, yi) is the top-right corner point of the i^th rectangle.

Design an algorithm to pick a random integer point inside the space covered by one of the given rectangles. A point on the perimeter of a rectangle is included in the space covered by the rectangle.

Any integer point inside the space covered by one of the given rectangles should be equally likely to be returned.

Note: An integer point is a point that has integer coordinates.

Implement the Solution class:

Solution(int[][] rects) Initializes the object with the given rectangles rects.
int[] pick() Returns a random integer point [u, v] inside the space covered by one of the given rectangles.

Input & Output

Example 1 — Single Rectangle

$ Input: rects = [[-2,-2,1,1]]

› Output: [0,-1] (one possible answer)

💡 Note: Single rectangle from (-2,-2) to (1,1). Any point within this rectangle is valid, such as (0,-1).

Example 2 — Multiple Rectangles

$ Input: rects = [[-2,-2,-1,-1], [1,0,3,2]]

› Output: [2,1] (one possible answer)

💡 Note: First rectangle has area 1, second has area 6. Point selection should be weighted by area, so second rectangle is 6 times more likely to be chosen.

Example 3 — Equal Area Rectangles

$ Input: rects = [[0,0,1,1], [2,2,3,3]]

› Output: [3,3] (one possible answer)

💡 Note: Both rectangles have equal area (4 points each), so each rectangle should be selected with equal probability.

Constraints

1 ≤ rects.length ≤ 100
rects[i].length == 4
-10⁹ ≤ a_i < x_i ≤ 10⁹
-10⁹ ≤ b_i < y_i ≤ 10⁹
x_i - a_i ≤ 2000
y_i - b_i ≤ 2000

Visualization

Tap to expand

Understanding the Visualization

Input Rectangles

Multiple non-overlapping rectangles with different sizes

Area-Weighted Selection

Select rectangle proportional to its area

Random Point

Pick random coordinates within selected rectangle

Key Takeaway

🎯 Key Insight: Weight rectangle selection by area to achieve uniform point distribution across all rectangles

Asked in

G Google 15 f Facebook 8 a Amazon 6

The key insight is to weight rectangle selection by area to ensure uniform point distribution. Best approach uses prefix sums with binary search for O(log n) rectangle selection. Time: O(log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Binary Search	O(log n)	O(n)	Weight rectangles by area using prefix sums for O(log n) selection
Uniform Rectangle Selection	O(1)	O(n)	Pick random rectangle uniformly, then random point within it

Prefix Sum with Binary Search — Algorithm Steps

Calculate area for each rectangle
Build prefix sum array
Generate random number in [0, total_area)
Binary search to find rectangle
Pick random point in selected rectangle

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Areas

Compute area for each rectangle

Build Prefix Sums

Cumulative sum of areas

Binary Search

Find rectangle by random point in total area

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct {
    int** rects;
    int* prefixSums;
    int rectCount;
} Solution;

Solution* createSolution(int** rects, int rectCount) {
    Solution* sol = malloc(sizeof(Solution));
    sol->rects = rects;
    sol->rectCount = rectCount;
    sol->prefixSums = malloc(rectCount * sizeof(int));
    
    int totalArea = 0;
    for (int i = 0; i < rectCount; i++) {
        int area = (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
        totalArea += area;
        sol->prefixSums[i] = totalArea;
    }
    
    srand(42);
    return sol;
}

int binarySearch(int* arr, int len, int target) {
    int left = 0, right = len - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int* pick(Solution* sol) {
    int target = (rand() % sol->prefixSums[sol->rectCount - 1]) + 1;
    int idx = binarySearch(sol->prefixSums, sol->rectCount, target);
    
    int* rect = sol->rects[idx];
    int* result = malloc(2 * sizeof(int));
    result[0] = rect[0] + (rand() % (rect[2] - rect[0] + 1));
    result[1] = rect[1] + (rand() % (rect[3] - rect[1] + 1));
    return result;
}

int* solution(int** rects, int rectCount) {
    Solution* sol = createSolution(rects, rectCount);
    return pick(sol);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for demo
    int** rects = malloc(10 * sizeof(int*));
    int rectCount = 0;
    
    // Parse first rectangle as example
    rects[0] = malloc(4 * sizeof(int));
    rects[0][0] = -2; rects[0][1] = -2; rects[0][2] = 1; rects[0][3] = 1;
    rectCount = 1;
    
    int* result = solution(rects, rectCount);
    printf("[%d,%d]\n", result[0], result[1]);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Binary search on prefix sums for rectangle selection

⚡ Linearithmic

Space Complexity

O(n)

Store rectangles and prefix sum array

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler