note0497.md

Leetcode 497. Random Point in Non-overlapping Rectangles

• Type: Math (random) + binary search
• Approach:
  • Similar to the problem 528. Random Pick with Weight
  1. Init function:
     • Use prefix sum to store the area of each rectangle
  2. Pick function:
     • Find a random area from 1 to the total area
     • Use binary search to search a specific area according to the random area
     • Calculate the coordinates by the area
• Complexity:
  • Time:
    1. Init:
       • O(n)
    2. Pick:
       • O(logn)
  • Space: O(n)