Count Number of Rectangles Containing Each Point - Binary Search [JS]

Description 

Solution: Binary Search

The constraints state that the height <= 10^9 and the width <= 100.
Given these constraints, we can do binary search on the x coordinates and loop through the y coordinates in a brute force manner.

To sum it up:

1. Group the rectangle coordinates by the y coordinate -> [[x coordinate, x coordinate, ...], [x coordinate, ...], ...]
2. Sort each of the buckets (because we need to binary search over them)
3. For each point, only loop through the buckets where the y coordinate >= the point's y coordinate.
   For each bucket, binary search to find the number of coordinates where the x coordinate is >= the point's x coordinate.

Time Complexity: O(n log(n) * 100) 627ms
Space Complexity: O(n)73.5MB

var countRectangles = function(rectangles, points) {
  let buckets = Array(101).fill(0).map(() => []);
  for (let [x, y] of rectangles) {
    buckets[y].push(x);
  }
  for (let i = 0; i < 101; i++) buckets[i].sort((a, b) => a - b);

  let res = [];
  for (let point of points) {
    let sum = 0;
    for (let j = point[1]; j < 101; j++) {
      // lowest index >= point[0]
      let index = lower_bound(buckets[j], point[0]);
      sum += buckets[j].length - index;
    }
    res.push(sum);
  }
  return res;

  function lower_bound(arr, targ) {
    let low = 0, high = arr.length;
    while (low < high) {
      let mid = Math.floor((low + high) / 2);
      if (arr[mid] >= targ) high = mid;
      else low = mid + 1;
    }
    return low;
  }
};

javascript