LeetCode 497 - Random Point in Non-overlapping Rectangles

The problem asks us to randomly pick an integer point from a set of non-overlapping rectangles in 2D space. Each rectangle is defined by its bottom-left (ai, bi) and top-right (xi, yi) corners.

leetcodemediumarraymathbinary-searchreservoir-samplingprefix-sumordered-setrandomized

LeetCode Problem 497

Difficulty: 🟡 Medium
Topics: Array, Math, Binary Search, Reservoir Sampling, Prefix Sum, Ordered Set, Randomized

Solution

Problem Understanding

The problem asks us to randomly pick an integer point from a set of non-overlapping rectangles in 2D space. Each rectangle is defined by its bottom-left (ai, bi) and top-right (xi, yi) corners. The goal is to ensure that every integer point inside the union of all rectangles has an equal probability of being selected. A point on the edge of a rectangle counts as part of the rectangle.

The input rects is a list of rectangles, each represented by four integers. The output is a randomly selected integer point [u, v] inside one of the rectangles. The constraints tell us there can be up to 100 rectangles, each with side lengths up to 2000, and the coordinates can be very large (up to 10^9 in magnitude). We may call the pick() function up to 10^4 times.

Important edge cases include rectangles with minimal area (like 1x1), rectangles that share edges but not overlap, and negative coordinates. The problem guarantees no overlap, so we do not have to handle overlapping areas.

Approaches

A brute-force solution would enumerate all integer points in all rectangles, store them in a list, and pick a random element from the list. This guarantees uniformity because each point appears exactly once. However, this approach is infeasible because the total number of points can reach 100 * 2001 * 2001, which is over 400 million points. The space and time complexity are too high for this input range.

The key insight for an optimal solution is that we do not need to enumerate every point. Instead, we can compute the number of points in each rectangle, maintain a prefix sum of these counts, and use it to pick a rectangle with probability proportional to its area. Once a rectangle is chosen, we can randomly select a point inside it using simple arithmetic. This reduces both memory usage and runtime drastically while preserving uniformity.

Approach Time Complexity Space Complexity Notes
Brute Force O(total_points) O(total_points) Enumerates all integer points
Optimal O(log n) per pick O(n) Uses prefix sum and binary search over rectangles

Algorithm Walkthrough

  1. Initialization: Compute the number of integer points in each rectangle. For rectangle [ai, bi, xi, yi], the number of points is (xi - ai + 1) * (yi - bi + 1). Store the cumulative sum of these counts in a list prefix_sum.
  2. Random Rectangle Selection: Generate a random integer k between 1 and the total number of points. Use binary search on the prefix_sum array to find which rectangle contains the k-th point.
  3. Random Point in Rectangle: Once a rectangle [ai, bi, xi, yi] is selected, generate a random integer dx in [0, xi - ai] and dy in [0, yi - bi]. The chosen point is (ai + dx, bi + dy).
  4. Return Result: Return the generated point as a list of two integers.

Why it works: The prefix sum ensures each rectangle is chosen with probability proportional to the number of integer points it contains. Picking a point uniformly within the rectangle guarantees each point is equally likely.

Python Solution

import random
from typing import List

class Solution:

    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.prefix_sum = []
        total = 0
        for x1, y1, x2, y2 in rects:
            points = (x2 - x1 + 1) * (y2 - y1 + 1)
            total += points
            self.prefix_sum.append(total)

    def pick(self) -> List[int]:
        k = random.randint(1, self.prefix_sum[-1])
        # Binary search to find the rectangle
        low, high = 0, len(self.prefix_sum) - 1
        while low < high:
            mid = (low + high) // 2
            if k <= self.prefix_sum[mid]:
                high = mid
            else:
                low = mid + 1
        rect_index = low
        x1, y1, x2, y2 = self.rects[rect_index]
        dx = random.randint(0, x2 - x1)
        dy = random.randint(0, y2 - y1)
        return [x1 + dx, y1 + dy]

The Python implementation first precomputes the prefix sum of points in each rectangle. Picking a random point involves selecting a rectangle with binary search and generating a random point inside it. This avoids generating all points, providing an efficient O(log n) pick time.

Go Solution

package main

import (
    "math/rand"
    "time"
)

type Solution struct {
    rects      [][]int
    prefixSum  []int
}

func Constructor(rects [][]int) Solution {
    rand.Seed(time.Now().UnixNano())
    prefix := make([]int, len(rects))
    total := 0
    for i, rect := range rects {
        x1, y1, x2, y2 := rect[0], rect[1], rect[2], rect[3]
        points := (x2 - x1 + 1) * (y2 - y1 + 1)
        total += points
        prefix[i] = total
    }
    return Solution{
        rects:     rects,
        prefixSum: prefix,
    }
}

func (this *Solution) Pick() []int {
    totalPoints := this.prefixSum[len(this.prefixSum)-1]
    k := rand.Intn(totalPoints) + 1

    // Binary search
    low, high := 0, len(this.prefixSum)-1
    for low < high {
        mid := (low + high) / 2
        if k <= this.prefixSum[mid] {
            high = mid
        } else {
            low = mid + 1
        }
    }
    rect := this.rects[low]
    x1, y1, x2, y2 := rect[0], rect[1], rect[2], rect[3]
    dx := rand.Intn(x2 - x1 + 1)
    dy := rand.Intn(y2 - y1 + 1)
    return []int{x1 + dx, y1 + dy}
}

The Go version mirrors Python closely. Differences include seeding the random number generator and using rand.Intn(n) which generates values [0, n). The +1 adjustments ensure inclusive ranges.

Worked Examples

Example Input: [[-2, -2, 1, 1], [2, 2, 4, 6]]

  1. Compute points: first rectangle (1-(-2)+1)*(1-(-2)+1) = 4*4=16, second rectangle (4-2+1)*(6-2+1)=3*5=15. Prefix sum [16, 31].
  2. Pick a random k between 1 and 31. Suppose k = 18.
  3. Binary search on [16, 31] gives rectangle 1 (second rectangle).
  4. Random point in second rectangle: dx = rand(0,2), dy = rand(0,4). Suppose dx=1, dy=2. Result [2+1,2+2]=[3,4].

Complexity Analysis

Measure Complexity Explanation
Time O(n) init, O(log n) per pick Init computes prefix sum; pick uses binary search
Space O(n) Stores prefix sum array

The pick operation does not depend on rectangle size, only the number of rectangles, which is efficient even for large rectangles.

Test Cases

# Example tests
sol = Solution([[-2, -2, 1, 1], [2, 2, 4, 6]])
for _ in range(5):
    point = sol.pick()
    assert len(point) == 2  # point has two coordinates
    x, y = point
    assert (-2 <= x <= 1 and -2 <= y <= 1) or (2 <= x <= 4 and 2 <= y <= 6)

# Edge case: single rectangle of size 1x1
sol = Solution([[0, 0, 0, 0]])
assert sol.pick() == [0, 0]

# Edge case: negative coordinates only
sol = Solution([[-5, -5, -1, -1]])
for _ in range(10):
    x, y = sol.pick()
    assert -5 <= x <= -1 and -5 <= y <= -1

# Multiple rectangles, varying sizes
sol = Solution([[0,0,1,1],[10,10,12,12],[5,5,5,5]])
for _ in range(10):
    x, y = sol.pick()
    assert (0 <= x <= 1 and 0 <= y <= 1) or (10 <= x <= 12 and 10 <= y <= 12) or (x == 5 and y == 5)
Test Why
Example rectangles Validates correct probability distribution and bounds
Single 1x1 rectangle Tests minimal rectangle handling
Negative coordinates Ensures