Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

Leetcode Random Point in Non-overlapping Rectangles problem solution

YASH PAL, 31 July 2024

In this Leetcode Random Point in Non-overlapping Rectangles problem solution 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.

Leetcode Random Point in Non-overlapping Rectangles problem solution

Problem solution in Python.

class Solution:

    def __init__(self, rects: List[List[int]]):
        self.ranges = ranges = [0]
        self.rects = rects
        for x1,y1,x2,y2 in rects:
            ranges.append( ranges[-1] + (y2-y1+1)*(x2-x1+1) )
    def pick(self) -> List[int]:
        ranges, rects = self.ranges, self.rects
        areaPt = random.randint(1,ranges[-1])
        x1,y1,x2,y2 = rects[bisect.bisect_left(ranges,areaPt)-1]
        return [random.randint(x1,x2), random.randint(y1,y2)]

Problem solution in Java.

class Solution {
    TreeMap<Integer, Integer> map;
    int size;
    int[][] rects;
    public Solution(int[][] rects) {
        map = new TreeMap<>();
        this.rects = rects;
        //rects[i] = [x1,y1,x2,y2]
        for(int i=0; i<rects.length; i++) {
            int[] rect = rects[i];
            map.put(size, i);
            size += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
        }
    }

    public int[] pick() {
        int ran = new Random().nextInt(size);
        int floorKey = map.floorKey(ran);
        int nth = ran - floorKey;
        return getCoordinate(rects[map.get(floorKey)], nth);
    }

    private int[] getCoordinate (int[] rect, int nth) {
        int x_length = rect[2] - rect[0] + 1;
        int y = nth / x_length;
        int x = nth % x_length;
        return new int[] {rect[0] + x, rect[1] + y};
    }
}

Problem solution in C++.

class Solution {
public:
    vector<int> np;
    vector<vector<int>> Rects;
    Solution(vector<vector<int>>& rects) {
        Rects = rects;
        for(auto rect : rects){
            int l1 = rect[2] - rect[0] + 1;
            int l2 = rect[3] - rect[1] + 1;
            int val = np.size() ? np.back() + (l1*l2) : l1*l2; 
            np.push_back(val);
        }
    }
    
    vector<int> pick() {
        int m = np.back();
        int r = rand() % m;
        auto it = upper_bound(np.begin(), np.end(), r);
        int rect = it - np.begin();  //end of step 1
        //step 2 begins
        vector<int> R = Rects[rect];
        int x = rand() % (R[2]-R[0]+1) + R[0];
        int y = rand() % (R[3]-R[1]+1) + R[1];
        return {x, y};
    }
};

coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes