Random Point in Non-overlapping Rectangles solution and explanation

import random

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.points = [0]
        for a, b, x, y in rects:
            self.points.append(self.points[-1] + (x - a + 1) * (y - b + 1))

    def pick(self) -> List[int]:
        random_point = random.randint(0, self.points[-1] - 1)
        rectangle_index = bisect.bisect_right(self.points, random_point) - 1
        a, b, x, y = self.rects[rectangle_index]
        width = x - a + 1
        height = y - b + 1
        base_in_rectangle = random_point - self.points[rectangle_index]
        dx = base_in_rectangle % width
        dy = base_in_rectangle // width
        return [a + dx, b + dy]

import java.util.*;

class Solution {
    int[] points;
    int[][] rects;
    Random rand;

    public Solution(int[][] rects) {
        this.rects = rects;
        this.points = new int[rects.length + 1];
        for (int i = 0; i < rects.length; i++) {
            int a = rects[i][0], b = rects[i][1], x = rects[i][2], y = rects[i][3];
            points[i + 1] = points[i] + (x - a + 1) * (y - b + 1);
        }
        rand = new Random();
    }

    public int[] pick() {
        int randPoint = rand.nextInt(points[rects.length]);
        int idx = Arrays.binarySearch(points, randPoint + 1) - 1;
        int[] rect = rects[idx];
        int a = rect[0], b = rect[1];
        int width = rect[2] - a + 1;
        int withinRect = randPoint - points[idx];
        int dx = withinRect % width;
        int dy = withinRect / width;
        return new int[] { a + dx, b + dy };
    }
}

#include <vector>
#include <cstdlib>
#include <algorithm>
#include <numeric>
using namespace std;

class Solution {
    vector<vector<int>> rects;
    vector<int> points;
public:
    Solution(vector<vector<int>>& rects) : rects(rects) {
        points.push_back(0);
        for (auto& rect : rects) {
            int a = rect[0], b = rect[1], x = rect[2], y = rect[3];
            points.push_back(points.back() + (x - a + 1) * (y - b + 1));
        }
    }

    vector<int> pick() {
        int rand_point = rand() % points.back();
        int idx = upper_bound(points.begin(), points.end(), rand_point) - points.begin() - 1;
        auto rect = rects[idx];
        int a = rect[0], b = rect[1];
        int width = rect[2] - a + 1;
        int within_rect = rand_point - points[idx];
        int dx = within_rect % width;
        int dy = within_rect / width;
        return {a + dx, b + dy};
    }
};

class Solution {
  constructor(rects) {
    this.rects = rects;
    this.points = [0];
    for (let rect of rects) {
      const [a, b, x, y] = rect;
      this.points.push(this.points[this.points.length - 1] + (x - a + 1) * (y - b + 1));
    }
  }

  pick() {
    let rand_point = Math.floor(Math.random() * this.points[this.points.length - 1]);
    let idx = this.points.findIndex(p => p > rand_point) - 1;
    const [a, b, x, y] = this.rects[idx];
    const width = x - a + 1;
    const within_rect = rand_point - this.points[idx];
    const dx = within_rect % width;
    const dy = Math.floor(within_rect / width);
    return [a + dx, b + dy];
  }
}

import random

class Solution:
    def __init__(self, rects):
        self.points_map = {}
        self.total_points = 0
        for a, b, x, y in rects:
            for i in range(a, x + 1):
                for j in range(b, y + 1):
                    self.points_map[self.total_points] = (i, j)
                    self.total_points += 1

    def pick(self):
        pick_index = random.randint(0, self.total_points - 1)
        return self.points_map[pick_index]

#include <map>
#include <vector>
#include <cstdlib>
using namespace std;

class Solution {
    map<int, pair<int, int>> points_map;
    int totalPoints = 0;
public:
    Solution(vector<vector<int>>& rects) {
        for (auto& rect : rects) {
            int a = rect[0], b = rect[1], x = rect[2], y = rect[3];
            for (int i = a; i <= x; ++i) {
                for (int j = b; j <= y; ++j) {
                    points_map[totalPoints++] = {i, j};
                }
            }
        }
    }

    vector<int> pick() {
        int pickIndex = rand() % totalPoints;
        return {points_map[pickIndex].first, points_map[pickIndex].second};
    }
};

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

func Constructor(rects [][]int) Solution {
	n := len(rects)
	s := make([]int, n+1)
	for i, v := range rects {
		s[i+1] = s[i] + (v[2]-v[0]+1)*(v[3]-v[1]+1)
	}
	return Solution{s, rects}
}

func (this *Solution) Pick() []int {
	n := len(this.rects)
	v := 1 + rand.Intn(this.s[len(this.s)-1])
	left, right := 0, n
	for left < right {
		mid := (left + right) >> 1
		if this.s[mid] >= v {
			right = mid
		} else {
			left = mid + 1
		}
	}
	rect := this.rects[left-1]
	x, y := rect[0]+rand.Intn(rect[2]-rect[0]+1), rect[1]+rand.Intn(rect[3]-rect[1]+1)
	return []int{x, y}
}