Skip to main content
Talentd

Random Point in Non-overlapping Rectangles - Solution & Explanation

MediumArrayMathBinary SearchReservoir Sampling10 min readAsked at: Uber, Google
Practice this problem

Problem Statement

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 ith rectangle and (xi, yi) is the top-right corner point of the ith 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 that 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.

 

Example 1:

Input
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
Output
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

Explanation
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // return [1, -2]
solution.pick(); // return [1, -1]
solution.pick(); // return [-1, -2]
solution.pick(); // return [-2, -2]
solution.pick(); // return [0, 0]

 

Constraints:

  • 1 <= rects.length <= 100
  • rects[i].length == 4
  • -109 <= ai < xi <= 109
  • -109 <= bi < yi <= 109
  • xi - ai <= 2000
  • yi - bi <= 2000
  • All the rectangles do not overlap.
  • At most 104 calls will be made to pick.

Approach Overview

Problem Overview: You are given several axis-aligned rectangles that do not overlap. Each call to pick() must return a random integer point from the union of these rectangles, where every valid point across all rectangles has equal probability.

Approach 1: Weighted Rectangle Selection Using Prefix Sum (Initialization: O(n), Pick: O(log n), Space: O(n))

Each rectangle contributes a number of integer points equal to (x2 - x1 + 1) * (y2 - y1 + 1). Treat rectangles as weighted buckets where the weight equals the number of points inside it. Build a prefix sum array of these areas during initialization. When pick() runs, generate a random integer in the range [1, totalPoints] and locate the rectangle containing that index using binary search. After selecting the rectangle, generate two random coordinates inside its bounds to produce the final point. This guarantees uniform probability across all integer points while keeping each pick efficient.

Approach 2: Uniform Randomized Area Selection (Initialization: O(n), Pick: O(n), Space: O(n))

This approach also computes the number of integer points inside each rectangle and stores cumulative areas. Instead of binary searching, you iterate through rectangles subtracting their area until the random index falls within a rectangle’s range. Once the rectangle is identified, generate random x and y coordinates within its bounds. The logic is simple and easy to implement, but rectangle lookup becomes linear. The technique still relies on uniform randomized sampling over total area.

Recommended for interviews: The prefix sum + binary search approach is the expected solution. It demonstrates understanding of weighted random sampling, array preprocessing, and efficient lookup. A linear scan works but scales poorly when pick() is called many times. Showing the brute logic first and then optimizing with prefix sums signals strong problem-solving skills.

Approach 1: Weighted Rectangle Selection Using Prefix Sum

This approach involves calculating the area (number of integer points) of each rectangle and using a prefix sum array to randomly select a rectangle based on these areas. After selecting a rectangle, a random point within that rectangle is generated.

In this implementation, we calculate the total number of integer points for each rectangle and build up a prefix sum array. When picking a point, a random index is generated and used to determine which rectangle the point falls into using binary search. A specific point within this rectangle is then selected by calculating its relative coordinates.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

Time Complexity: O(log n) for picking a point due to binary search, where n is the number of rectangles.
Space Complexity: O(n) for storing prefix sums, where n is the number of rectangles.

Try this approach in the editor →

Approach 2: Uniform Randomized Area Selection

In this approach, a hash map is used to store all possible integer point coordinates in rectangles. A random point is accessed directly by randomly selecting a key from the hash map. However, this solution is not optimal due to time and space requirements.

This Python solution precomputes every possible point across all rectangles into a hash map. When picking, it simply picks one key directly from the hash map, which leads to high memory usage and unwieldy initialization.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(1) for picking, assuming map insertion and access time is constant.
Space Complexity: O(m*n), where m and n are the width and height of the largest rectangle.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Weighted Rectangle Selection Using Prefix Sum

Time Complexity: O(log n) for picking a point due to binary search, where n is the number of rectangles.
Space Complexity: O(n) for storing prefix sums, where n is the number of rectangles.

Uniform Randomized Area Selection

Time Complexity: O(1) for picking, assuming map insertion and access time is constant.
Space Complexity: O(m*n), where m and n are the width and height of the largest rectangle.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Weighted Rectangle Selection Using Prefix SumInit: O(n), Pick: O(log n)O(n)Best general solution when pick() is called frequently
Uniform Randomized Area Selection (Linear Scan)Init: O(n), Pick: O(n)O(n)Simpler implementation when number of rectangles is small

Video Solution

Random Point in Non-overlapping Rectangles | LeetCode 497 | C++, Python • Knowledge Center • 6,421 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Random Point in Non-overlapping Rectangles easy or hard?
The problem is rated Medium because the key challenge is recognizing it as a weighted random sampling problem. Once the idea of mapping rectangle area to probability is clear, prefix sums and binary search provide a clean and efficient implementation.
Random Point in Non-overlapping Rectangles Python/Java solution
Implement a class that stores rectangles and a prefix sum of their areas. During pick(), generate a random integer within the total area, binary search the prefix array to locate the rectangle, and randomly select x and y coordinates within that rectangle. The same logic works across Python, Java, C++, and JavaScript.
How to solve Random Point in Non-overlapping Rectangles in O(n)?
An O(n) per-pick approach generates a random number within the total area and linearly scans rectangles until the corresponding cumulative area range is found. After selecting the rectangle, random x and y coordinates are generated inside its bounds. Initialization still takes O(n).
What is the best approach for Random Point in Non-overlapping Rectangles?
The most efficient solution uses weighted rectangle selection with a prefix sum array and binary search. Each rectangle is weighted by the number of integer points it contains. A random index across the total area is generated, and binary search finds the corresponding rectangle in O(log n) time.
Is Random Point in Non-overlapping Rectangles asked at Google/Amazon/Meta?
Random sampling and weighted probability problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving weighted random selection, prefix sums, or reservoir sampling are commonly tested in system design and algorithm rounds.
What data structure is used in Random Point in Non-overlapping Rectangles?
The main data structure is an array storing prefix sums of rectangle areas. This allows mapping a random index to a rectangle efficiently using binary search. The rectangles themselves are stored in an array for constant-time coordinate generation.
What is the time complexity of Random Point in Non-overlapping Rectangles?
Building the prefix sum array takes O(n) time during initialization. Each call to pick() runs in O(log n) using binary search to locate the rectangle, followed by O(1) random coordinate generation. Space complexity is O(n) for storing cumulative areas.

Ready to solve this problem?

Practice Random Point in Non-overlapping Rectangles with our built-in code editor and test cases.

Practice on FleetCode
Previous

Generate Random Point in a Circle

Next

Random Pick with Weight