Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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]

Solution

Caution - Randomly Picking Rectangle and Then Point in it Will Not Work

An intuitive solution is to randomly select one rectangle from the rects and then generate a random point within it. However, this method is flawed. Why?

Consider two rectangles, R1 and R2, where R1 has a larger area than R2.

Let S1 represent the set of points within rectangle R1, and S2 the set of points within rectangle R2. Mathematically, we have:

1
2
3

S1 = {p11, p12, p13, ........................, p1n}
S2 = {p21, p22, p23, ......, p2m}
n > m

It is clear that R1 has a larger area than R2, so S1 contains more points than S2 (i.e., n > m).

To randomly pick an integer point within the area covered by one of the given rectangles, simply selecting a rectangle randomly won’t work; the area of each rectangle must be considered.

Method 1 - Pick Rectangle First Using Area and TreeMap and Then Point using Using TreeMap.ceilingKey()

We can do following:

  • map: Stores cumulative area as keys and rectangle indices as values.
  • rects: Stores the input array of rectangles.
  • totalArea: Stores the sum of the areas of all rectangles.
  • rnd: A Random object for generating random numbers.

Now, we can follow these steps:

  1. Initialize rects: Store the input array of rectangles.
  2. Initialize map: Create a new TreeMap.
  3. Initialize totalArea: Set the total area to 0.
  4. Calculate Areas and Populating the Map:
    • Iterate over each rectangle to calculate its area.
    • Update totalArea to include the area of the current rectangle.
    • Map the cumulative area to the rectangle’s index in the map.
  5. Generate Random Area Index:
    • Generate a random number between 0 and totalArea - 1, then add 1 to shift the range to [1, totalArea].
    • Use ceilingKey to find the smallest key in the map greater than or equal to this random number (c). This key points to the rectangle that should be picked.
  6. Pick a Random Point in the Rectangle:
    • Retrieve the rectangle index from the map using c.
    • Call pickInRect with the selected rectangle to return a random point within it.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    private TreeMap<Integer, Integer> map;
    private int[][] rects;
    private int totalArea;
    private Random rnd= new Random();

	// rect[0] = left,  rect[1] = bottom
	// rect[2] = right, rect[3] = top
    public Solution(int[][] rects) {
        this.rects = rects;
        map = new TreeMap<>();
        totalArea = 0;
        
        for(int i = 0; i < rects.length; i++) {
            int[] rect = rects[i];
						
            // the right part means the number of points can be picked in this rectangle
            totalArea += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
			
            map.put(totalArea, i);
        }
    }
    
    public int[] pick() {
		// nextInt(sum) returns a num in [0, sum -1]. After added by 1, it becomes [1, sum]
		int c = map.ceilingKey(rnd.nextInt(totalArea) + 1);
        
        return pickInRect(rects[map.get(c)]);
    }
    
    private int[] pickInRect(int[] rect) {
        int left = rect[0], right = rect[2], bottom = rect[1], top = rect[3];
        int x = left + rnd.nextInt(right - left + 1);
        int y = bottom + rnd.nextInt(top - bottom + 1);
        return new int[]{x, y};
    }
}

Complexity

Constructor: Solution(int[][] rects)

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Method: int[] pick()

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)

Method 2 - Pick Rectangle First Using Area and TreeMap and Then Point using Using TreeMap.floorKey()

We are also saving rectangle in the map, instead of saving rects array. Here are the steps:

  1. Class Initialization:

    • Define a TreeMap<Integer, int[]> areaToRectMap to map cumulative areas to rectangles.
    • Initialize totalArea to 0.
    • Initialize a Random object rand for generating random numbers.

  2. Constructor:

    • Initialize areaToRectMap, totalArea, and rand.
    • Call buildMap() to populate the areaToRectMap.

  3. buildMap Method:

    • Iterate through each rectangle in rects.
    • Calculate the area of each rectangle.
    • Map the cumulative area to the rectangle in areaToRectMap.
    • Update totalArea with the area of the current rectangle.

  4. pick Method:

    • Generate a random integer currIdx between 0 and totalArea - 1.
    • Find the largest key in areaToRectMap less than or equal to currIdx using floorKey.
    • Retrieve the rectangle associated with this key.
    • Call getRandomPoint to generate a random point within the selected rectangle.

  5. getRandomPoint Method:

    • Generate a random x-coordinate within the rectangle’s x-range.
    • Generate a random y-coordinate within the rectangle’s y-range.
    • Return the coordinates as an array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
	private final TreeMap<Integer, int[] > areaToRectMap;
	private int totalArea;
	private final Random rand;

	public Solution(int[][] rects) {
		this.idx = 0;
		this.areaToRectMap = new TreeMap<>();
		buildMap();
		this.rand = new Random();
	}

	private void buildMap() {
		for (int[] rect: rects) {
			int area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
			idxRectMap.put(idx, rect);
			totalArea += area;
		}
	}

	public int[] pick() {
		int currIdx = rand.nextInt(totalArea);
		int keyIdx = areaToRectMap.floorKey(currIdx);
		int[] rect = areaToRectMap.get(keyIdx);
		return getRandomPoint(rect);
	}

	private int[] getRandomPoint(int[] rect) {
		int[] point = new int[2];
		point[0] = rand.nextInt(rect[2] - rect[0] + 1) + rect[0];
		point[1] = rand.nextInt(rect[3] - rect[1] + 1) + rect[1];
		return point;
	}
}

Complexity

Constructor: Solution(int[][] rects)

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Method: int[] pick()

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)

Method 3 - Reusing Area to Pickup the Point in Rectangle:

Also, we are saving rect[] inside the map, rather than the index earlier. Here are the steps:

  1. Class Initialization:
    • Define a TreeMap<Integer, int[]> map to map cumulative areas to rectangles.
    • Initialize totalArea to zero.
    • Create a Random object rand for generating random numbers.
  2. Constructor:
    • Iterate over each rectangle in the rects array:
      • Calculate the area of the rectangle.
      • Add the rectangle’s cumulative area to totalArea.
      • Store the cumulative area as the key and the rectangle as the value in map.
  3. pick Method:
    • Generate a random integer randArea between 0 and totalArea - 1.
    • Use higherKey to find the smallest key greater than randArea in map.
    • Retrieve the rectangle associated with this key from map.
    • Compute the difference between the selected cumulative area and randArea.
    • Calculate the width of the rectangle.
    • Determine random x and y coordinates within the rectangle using the difference.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
        TreeMap<Integer, int[]> map = new TreeMap<>();
        Random rand = new Random();
        int totalArea;

        public Solution(int[][] rects) {
            this.totalArea = 0;
            for (int[] rect : rects) {
	            // +1 as we need to consider edges also.
                totalArea += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
                map.put(totalArea, rect);
            }
        }

        public int[] pick() {
            int randArea = rand.nextInt(totalArea);
            int key = map.higherKey(randArea);
            int[] rect = map.get(key);

            int diff = key - randArea - 1;
            int width = (rect[2] - rect[0] + 1);

            int x = rect[0] + diff % width;
            int y = rect[1] + diff / width;

            return new int[]{x, y};
        }
}

Complexity

Constructor: Solution(int[][] rects)

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Method: int[] pick()

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)