We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Number of Rectangles Containing Each Point

Number: 2333

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of rectangles where each rectangle is represented by [length, height] and all rectangles are anchored at (0, 0), along with an array of points [x, y], determine for each point the number of rectangles that contain it. A rectangle contains a point if and only if 0 <= x <= length and 0 <= y <= height.

Key Insights

  • The y-coordinate of rectangles (height) is limited (1 <= height <= 100) even though the length can be as large as 10^9.
  • You can group rectangles by their height which allows processing queries by iterating only over heights that are large enough.
  • For rectangles with a given height, store their lengths in a sorted list so that binary search can be used to count how many rectangles have length >= x for a given point.
  • For each query point (x, y), iterate over all possible heights from y up to 100 and use binary search to quickly count the qualified rectangles.

Space and Time Complexity

Time Complexity: O(P * H * log(R/H)) where P is the number of points, H is the maximum height (bounded by 100) and R/H is the average number of rectangles per height group. Space Complexity: O(R) for storing the rectangle lengths grouped by height.

Solution

The strategy is to preprocess the input rectangles by grouping them based on their heights. For each height, we maintain a sorted list of the corresponding rectangle lengths. When processing a point (x, y), we consider every rectangle group with height >= y and perform a binary search on the sorted list to count how many rectangle lengths are >= x. By summing the counts over these groups, we obtain the total number of rectangles containing that point. This approach leverages the relatively small range of possible heights to reduce unnecessary work compared to scanning all rectangles for every point.

Code Solutions

# Python solution

import bisect
from collections import defaultdict

def countRectangles(rectangles, points):
    # Group rectangle lengths by height.
    height_to_lengths = defaultdict(list)
    for length, height in rectangles:
        height_to_lengths[height].append(length)
    
    # Sort the lengths list for each height for binary search.
    for h in height_to_lengths:
        height_to_lengths[h].sort()
    
    # Precompute an array for heights 1 to 100 to avoid checking missing groups.
    height_groups = [height_to_lengths[h] if h in height_to_lengths else [] for h in range(101)]
    
    result = []
    # Process each point.
    for x, y in points:
        count = 0
        # Iterate through all valid heights from y to 100.
        for h in range(y, 101):
            lengths = height_groups[h]
            if lengths:
                # Find first index in 'lengths' where rectangle length >= x.
                idx = bisect.bisect_left(lengths, x)
                count += len(lengths) - idx
        result.append(count)
    return result

# Example usage
rectangles = [[1,2],[2,3],[2,5]]
points = [[2,1],[1,4]]
print(countRectangles(rectangles, points))
← Back to All Questions