Count Number of Rectangles Containing Each Point

Problem Description

You are given a 2D integer array rectangles where rectangles[i] = [l_i, h_i] indicates that the i-th rectangle has a length of l_i and a height of h_i. You are also given a 2D integer array points where points[j] = [x_j, y_j] is a point with coordinates (x_j, y_j). The i-th rectangle has its bottom-left corner point at the coordinates (0, 0) and its top-right corner point at (l_i, h_i). Return an integer array count of length points.length where count[j] is the number of rectangles that contain the j-th point.

Key Insights

• A rectangle contains a point if the point's coordinates are within the rectangle's bounds, including the edges.
• The problem can potentially involve a large number of rectangles and points, making a naive O(n * m) solution inefficient.
• We can utilize sorting and binary search to efficiently count the number of rectangles containing each point.

Space and Time Complexity

Time Complexity: O(n log n + m log m) where n is the number of rectangles and m is the number of points. Space Complexity: O(n + m) for storing the sorted rectangles and results.

Solution

To solve the problem, we can take the following steps:

1. Sort the rectangles based on their lengths and heights.
2. For each point, use binary search to determine how many rectangles have lengths greater than or equal to the point's x-coordinate.
3. Count how many of those rectangles also have heights greater than or equal to the point's y-coordinate.

By leveraging sorting and binary search, we can efficiently count the rectangles that contain each point.

Code Solutions