algoadvance

Leetcode 497. Random Point in Non

Problem Statement

Given a list of non-overlapping axis-aligned rectangles rects, write a function that randomly and uniformly picks an integer point in the space covered by the rectangles.

Each rectangle rects[i] is represented as a list, [x1, y1, x2, y2], where (x1, y1) is the coordinate of its bottom-left corner and (x2, y2) is the coordinate of its top-right corner.

You need to implement the class Solution and the function pick() such that each point in the rectangles is chosen with uniform randomness.

class Solution {

    public Solution(int[][] rects) {
        
    }
    
    public int[] pick() {
        
    }
}

Clarifying Questions

1. Are rectangles non-overlapping and axis-aligned?
   • Yes, all rectangles are non-overlapping and axis-aligned.
2. Are there constraints on the range of coordinates for rectangles?
   • The coordinates can be large, fitting within the typical range for integer coordinates.
3. How frequently is the pick() function called relative to initialization?
   • This isn’t specified, but we’d aim to make both reasonable in performance.
4. Do the rectangles include their boundary points?
   • Yes, the edges of the rectangles are included in the points that can be chosen.

Strategy

1. Pre-computation:
   • For each rectangle, calculate the total number of points it contains, which is (x2 - x1 + 1) * (y2 - y1 + 1).
   • Keep a cumulative sum array of these point counts to help quickly pick a rectangle based on its area.
2. Random Selection:
   • To pick a point, first randomly select one rectangle based on the pre-computed weights.
   • Then, pick a random point within the chosen rectangle using the uniform range of its coordinates.

Code Implementation

import java.util.Random;

class Solution {
    private int[][] rects;
    private int[] areas;
    private int totalArea;
    private Random rand;

    public Solution(int[][] rects) {
        this.rects = rects;
        this.areas = new int[rects.length];
        this.totalArea = 0;
        this.rand = new Random();
        
        // Pre-compute the area (number of points) for each rectangle
        for (int i = 0; i < rects.length; i++) {
            int[] rect = rects[i];
            int area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            totalArea += area;
            areas[i] = totalArea;  // This keeps a cumulative sum of areas
        }
    }
    
    public int[] pick() {
        int target = rand.nextInt(totalArea);  // Pick a random area position
        int low = 0, high = areas.length - 1;
        
        // Binary search to find the rectangle corresponding to the target
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (areas[mid] > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        
        // Low now points to the rectangle we need
        int[] rect = rects[low];

        // Calculate random coordinates inside the found rectangle
        int x = rect[0] + rand.nextInt(rect[2] - rect[0] + 1);
        int y = rect[1] + rand.nextInt(rect[3] - rect[1] + 1);
        
        return new int[]{x, y};
    }
}

Time Complexity

• Initialization (Solution constructor):
  • Pre-computation of areas takes (O(n)) time, where (n) is the number of rectangles.
• Pick Method:
  • Random number generation: (O(1)).
  • Binary Search: (O(\log n)) where (n) is the number of rectangles.
  • Random point selection within the rectangle: (O(1)).

Overall, the pick method has a time complexity of (O(\log n)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?