Count Number of Rectangles Containing Each Point

Medium

Asked by:

2 views

Topics:

Arrays

You are given a 2D integer array rectangles where rectangles[i] = [l_i, h_i] indicates that 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.

The i^th rectangle contains the j^th point if 0 <= x_j <= l_i and 0 <= y_j <= h_i. Note that points that lie on the edges of a rectangle are also considered to be contained by that rectangle.

Example 1:

Input: rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
Output: [2,1]
Explanation: 
The first rectangle contains no points.
The second rectangle contains only the point (2, 1).
The third rectangle contains the points (2, 1) and (1, 4).
The number of rectangles that contain the point (2, 1) is 2.
The number of rectangles that contain the point (1, 4) is 1.
Therefore, we return [2, 1].

Example 2:

Input: rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]
Output: [1,3]
Explanation:
The first rectangle contains only the point (1, 1).
The second rectangle contains only the point (1, 1).
The third rectangle contains the points (1, 3) and (1, 1).
The number of rectangles that contain the point (1, 3) is 1.
The number of rectangles that contain the point (1, 1) is 3.
Therefore, we return [1, 3].

Constraints:

1 <= rectangles.length, points.length <= 5 * 10⁴
rectangles[i].length == points[j].length == 2
1 <= l_i, x_j <= 10⁹
1 <= h_i, y_j <= 100
All the rectangles are unique.
All the points are unique.

Try coding it in LeetCode

Count Number of Rectangles Containing Each Point

Medium

Asked by:

2 views

Topics:

Arrays

You are given a 2D integer array rectangles where rectangles[i] = [l_i, h_i] indicates that 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.

The i^th rectangle contains the j^th point if 0 <= x_j <= l_i and 0 <= y_j <= h_i. Note that points that lie on the edges of a rectangle are also considered to be contained by that rectangle.

Example 1:

Input: rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
Output: [2,1]
Explanation: 
The first rectangle contains no points.
The second rectangle contains only the point (2, 1).
The third rectangle contains the points (2, 1) and (1, 4).
The number of rectangles that contain the point (2, 1) is 2.
The number of rectangles that contain the point (1, 4) is 1.
Therefore, we return [2, 1].

Example 2:

Input: rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]
Output: [1,3]
Explanation:
The first rectangle contains only the point (1, 1).
The second rectangle contains only the point (1, 1).
The third rectangle contains the points (1, 3) and (1, 1).
The number of rectangles that contain the point (1, 3) is 1.
The number of rectangles that contain the point (1, 1) is 3.
Therefore, we return [1, 3].

Constraints:

1 <= rectangles.length, points.length <= 5 * 10⁴
rectangles[i].length == points[j].length == 2
1 <= l_i, x_j <= 10⁹
1 <= h_i, y_j <= 100
All the rectangles are unique.
All the points are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum values for the x and y coordinates of the rectangles and points, and what is the maximum number of rectangles and points?
Can the coordinates of the rectangles and points be floating-point numbers, or are they always integers?
If a point lies exactly on the border of a rectangle (or on a corner), should it be considered as 'contained' within that rectangle?
Can the input arrays (rectangles and points) be empty or null?
Is the order of the output array (the count of containing rectangles for each point) expected to match the order of points in the input array points?

Brute Force Solution

Approach

The brute force approach for this rectangle problem is to check every rectangle against every point. We'll go through each point one by one, and for each point, we'll count how many rectangles contain it.

Here's how the algorithm would work step-by-step:

Take the first point we need to check.
Now, look at the first rectangle.
Check if that rectangle contains the point.
If it does, increase our count.
If not, move on.
Repeat this process (checking if the rectangle contains the point and updating the count) for every rectangle we have.
Once we've checked all the rectangles, we know how many rectangles contain that first point. Write down that number.
Now, move to the next point and repeat the entire process (checking against all rectangles and counting).
Continue this until we have counted the number of rectangles containing each point.

Code Implementation

def count_rectangles_containing_each_point(rectangles, points):
    number_of_rectangles_containing_point = []
    for point_index in range(len(points)):
        point = points[point_index]
        count = 0

        # Iterate through each rectangle to check if it contains the current point
        for rectangle_index in range(len(rectangles)):
            rectangle = rectangles[rectangle_index]

            # Check if the point is within the bounds of the rectangle
            if rectangle[0] <= point[0] and rectangle[1] <= point[1]:
                count += 1

        number_of_rectangles_containing_point.append(count)

    return number_of_rectangles_containing_point

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of points and m be the number of rectangles. For each point, we iterate through all rectangles to check if the point is contained within the rectangle. This involves iterating through all 'n' points and for each point iterating through all 'm' rectangles. Thus, the time complexity is O(n*m).

Space Complexity

O(1) – The provided brute force approach iterates through each point and each rectangle. It maintains a counter variable for each point to track the number of rectangles containing it. The number of points and rectangles are inputs, but the counter itself occupies constant space. Therefore, the auxiliary space required is independent of the input size, meaning it's constant.

Optimal Solution

Approach

The efficient strategy involves sorting the rectangles to help us quickly find the ones that could possibly contain a given point. Then, for each point, we efficiently count how many rectangles actually do contain it, using the sorted information to skip unnecessary checks.

Here's how the algorithm would work step-by-step:

First, organize the rectangles based on their heights from tallest to shortest. This will help us later.
Then, for each point we want to check, use a method that helps us to quickly find the rectangles whose heights are tall enough to possibly contain the point. Because we sorted the rectangles, we can quickly find the 'cutoff' point in our sorted list of rectangle heights.
From this subset of rectangles, only check the rectangles that are as wide or wider than the point's horizontal position. If a rectangle is wide and tall enough, it must contain the point, so we add it to our count.
Continue this process for each point, and the result will be a list of the number of rectangles that contain each respective point.

Code Implementation

def count_rectangles(rectangles, points):
    rectangle_counts = []

    # Sort rectangles by height in descending order.
    rectangles.sort(key=lambda x: x[1], reverse=True)

    for point_x, point_y in points:
        count = 0
        
        # Iterate through sorted rectangles.
        for rectangle_x, rectangle_y in rectangles:
            # Skip rectangles that are too short.
            if rectangle_y < point_y:
                break

            # Only count rectangles that contain the point.
            if rectangle_x >= point_x:
                count += 1

        rectangle_counts.append(count)

    return rectangle_counts

Big(O) Analysis

Time Complexity

O(n log n + m log n) – Sorting the rectangles by height takes O(n log n) time, where n is the number of rectangles. For each of the m points, we perform a binary search (log n) to find the rectangles with sufficient height. Then, for each point, we iterate through a subset of the rectangles to count how many contain the point, which in the worst case could be all n rectangles. Considering both sorting and point checking, the overall time complexity is O(n log n + m * (log n + k)), where k is the number of rectangles that could potentially contain the point. If k is close to n, the complexity becomes O(n log n + m * n). A tighter bound that accounts for early exits due to the initial sorting is O(n log n + m log n) if the heights of points are evenly distributed because we only iterate through subset of rectangles. If k is relatively small compared to n, the time complexity is approximately O(n log n + m log n).

Space Complexity

O(N) – The algorithm sorts the rectangles based on height. This sorting operation, depending on the implementation (e.g., merge sort, Timsort), might require auxiliary space proportional to the number of rectangles, where N is the number of rectangles. Additionally, the algorithm creates a list to store the counts of rectangles containing each point, where the length of this list is equal to the number of points. Therefore, the space complexity is dominated by the sorting algorithm auxiliary space and the storage of result, both of which can be up to O(N). So, overall the space complexity is O(N).

Edge Cases

Case	How to Handle
rectangles array is null or empty	Return an empty array of counts immediately, as there are no rectangles to consider.
points array is null or empty	Return an empty array of counts immediately, as there are no points to check.
rectangles array contains rectangles with zero area (e.g., height or width is zero)	These rectangles should not contribute to the count and the solution should ignore them or handle them gracefully, potentially by skipping them in the area calculation.
points array contains points with very large coordinates (close to integer limits)	Ensure calculations (e.g., comparing coordinates) don't cause integer overflow by using appropriate data types (e.g., long).
rectangles array contains rectangles with negative coordinates	The problem statement typically assumes non-negative coordinates; clarify the expected behavior (either reject negative coordinates or interpret them correctly based on the desired coordinate system).
All points lie outside all rectangles	The expected output array will contain all zeros; the algorithm should correctly handle this scenario without errors.
All points lie inside all rectangles	The expected output array will contain the total number of rectangles for each point; the algorithm should compute this correctly.
The number of rectangles and points is very large (close to the maximum constraints)	Consider the time and space complexity; an O(n*m) solution (n rectangles, m points) might be too slow; optimize by sorting or using spatial indexing if necessary.