What is the time complexity of Count Number of Rectangles Containing Each Point?

The optimal solution has a time complexity of O(m*n + m*log(m) + p*m).

What is the space complexity of Count Number of Rectangles Containing Each Point?

The space complexity is O(m + p).

What data structures are used to solve Count Number of Rectangles Containing Each Point?

This problem uses Array, Hash Table, Binary Search, Binary Indexed Tree, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Count Number of Rectangles Containing Each Point?

Insight 1: Sorting rectangles by height and using binary search can efficiently determine how many rectangles contain a point. Insight 2: Processing points and rectangles by height, from highest to lowest, enables us to maintain a sorted list of rectangle lengths encountered so far, and quickly query how many of them contain a given point's x-coordinate.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Count Number of Rectangles Containing Each Point - LeetCode 2250 Solution

Q: How to solve Count Number of Rectangles Containing Each Point?

The solution uses a combination of bucket sort (based on the height of rectangles and y-coordinate of points) and binary search. First, rectangles are grouped by their heights into a list of lists. Then each list is sorted by the length of the rectangles. Points are also grouped by their y-coordinates. We iterate through the heights from 100 down to 1. At each height, we merge the lengths of the rectangles at that height with a list of rectangle lengths encountered so far. Finally, for each point with y-coordinate equal to the current height, we use binary search to determine the number of rectangle lengths in our lengths_so_far that are greater than or equal to the point's x-coordinate. This counts the number of rectangles containing the point. The result for each point is stored in the output array.

Count Number of Rectangles Containing Each Point - Complete Solution Guide

Count Number of Rectangles Containing Each Point is LeetCode problem 2250, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Framing

Count Number of Rectangles Containing Each Point is a Medium LeetCode problem that rewards careful tracing, edge-case handling, and a clear grasp of Array and Hash Table. The best solutions usually explain why the chosen invariant holds before they optimize for time or space.

Quick Example Mindset

A useful way to test Count Number of Rectangles Containing Each Point is to start with a tiny input that exposes the boundary conditions, then run the same logic on a slightly larger case to verify the array behavior and the hash table interaction. That second pass is where off-by-one mistakes and missing updates usually appear.

Problem Statement

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 c

Detailed Explanation

The problem asks us to count, for each given point (x, y), how many rectangles from a given list of rectangles contain that point. Each rectangle is defined by its top-right corner (l, h), assuming its bottom-left corner is at (0, 0). A rectangle contains a point (x, y) if 0 <= x <= l and 0 <= y <= h. The input consists of two arrays: `rectangles` (length, height) and `points` (x, y). The output should be an array `count` where `count[i]` represents the number of rectangles containing the i-th point.

Solution Approach

The solution uses a combination of bucket sort (based on the height of rectangles and y-coordinate of points) and binary search. First, rectangles are grouped by their heights into a list of lists. Then each list is sorted by the length of the rectangles. Points are also grouped by their y-coordinates. We iterate through the heights from 100 down to 1. At each height, we merge the lengths of the rectangles at that height with a list of rectangle lengths encountered so far. Finally, for each point with y-coordinate equal to the current height, we use binary search to determine the number of rectangle lengths in our lengths_so_far that are greater than or equal to the point's x-coordinate. This counts the number of rectangles containing the point. The result for each point is stored in the output array.

Step-by-Step Algorithm

Step 1: Create a list of lists, `rects_by_height`, to store rectangles grouped by their heights. Iterate through the `rectangles` array, placing the length of each rectangle into the list corresponding to its height.
Step 2: Sort the lengths of the rectangles within each height's list in `rects_by_height` in ascending order.
Step 3: Create a list of lists, `points_by_y`, to store points grouped by their y-coordinates. Store each point's x-coordinate and its original index within the points array.
Step 4: Initialize the `ans` array, which will store the result for each point.
Step 5: Initialize lengths_so_far, which store the rectangle lengths from heights greater than or equal to current height, in sorted order.
Step 6: Iterate through the heights from 100 down to 1. For each height:
Step 7: Merge new_lengths (rects at current height) with lengths_so_far into lengths_so_far maintaining sorted order
Step 8: Iterate through the points with y-coordinate equal to the current height. For each point, use binary search in lengths_so_far to find the index of the first length that is greater than or equal to the point's x-coordinate.
Step 9: The number of rectangles containing the point is the number of lengths in lengths_so_far that are greater than or equal to the point's x-coordinate, which is the length of lengths_so_far minus the index found in the previous step. Store this value in the `ans` array at the original index of the point.
Step 10: Return the `ans` array.

Key Insights

Insight 1: Sorting rectangles by height and using binary search can efficiently determine how many rectangles contain a point.
Insight 2: Processing points and rectangles by height, from highest to lowest, enables us to maintain a sorted list of rectangle lengths encountered so far, and quickly query how many of them contain a given point's x-coordinate.
Insight 3: The height constraint (1 <= h_i, y_j <= 100) allows for the use of bucket sort (or counting sort) for grouping rectangles and points by their y-coordinates which improves performance.

Complexity Analysis

Time Complexity: O(m*n + m*log(m) + p*m)

Space Complexity: O(m + p)

Topics

This problem involves: Array, Hash Table, Binary Search, Binary Indexed Tree, Sorting.

Study Paths

Continue from this problem into the surrounding topic and company clusters to compare how the same pattern appears in other interview settings.

Related topics: Array, Hash Table, Binary Search, Binary Indexed Tree

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

Count Number of Rectangles Containing Each Point | LeetCode 2250

Medium

Array Hash Table Binary Search Binary Indexed Tree Sorting

Study Path

Browse topics

Continue through the pattern hub for deeper coverage and neighboring problem variants.

Array Hash Table Binary Search Binary Indexed Tree Sorting

Company Signals

Browse companies

Review the companies that ask this problem and move into adjacent interview sets.

No company matches yet.

Time: O(m*n + m*log(m) + p*m)Space: O(m + p)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] countRectangles(int[][] rectangles, int[][] points) {
        List<List<Integer>> rects_by_height = new ArrayList<>();
        for (int i = 0; i <= 100; i++) {
            rects_by_height.add(new ArrayList<>());
        }
        for (int[] rect : rectangles) {
            int l = rect[0];
            int h = rect[1];
            rects_by_height.get(h).add(l);
        }

        for (int h = 1; h <= 100; h++) {
            Collections.sort(rects_by_height.get(h));
        }

        List<List<Pair>> points_by_y = new ArrayList<>();
        for (int i = 0; i <= 100; i++) {
            points_by_y.add(new ArrayList<>());
        }
        for (int i = 0; i < points.length; i++) {
            int x = points[i][0];
            int y = points[i][1];
            points_by_y.get(y).add(new Pair(x, i));
        }

        int[] ans = new int[points.length];

        List<Integer> lengths_so_far = new ArrayList<>();
        for (int h = 100; h > 0; h--) {
            List<Integer> new_lengths = rects_by_height.get(h);
            if (new_lengths.size() > 0) {
                List<Integer> merged_list = new ArrayList<>();
                int p1 = 0;
                int p2 = 0;
                while (p1 < lengths_so_far.size() && p2 < new_lengths.size()) {
                    if (lengths_so_far.get(p1) < new_lengths.get(p2)) {
                        merged_list.add(lengths_so_far.get(p1));
                        p1++;
                    } else {
                        merged_list.add(new_lengths.get(p2));
                        p2++;
                    }
                }
                merged_list.addAll(lengths_so_far.subList(p1, lengths_so_far.size()));
                merged_list.addAll(new_lengths.subList(p2, new_lengths.size()));
                lengths_so_far = merged_list;
            }

            for (Pair p : points_by_y.get(h)) {
                int x = p.x;
                int original_idx = p.index;
                int idx = binarySearch(lengths_so_far, x);
                ans[original_idx] = lengths_so_far.size() - idx;
            }
        }

        return ans;
    }
    
    private int binarySearch(List<Integer> list, int target) {
        int low = 0;
        int high = list.size() - 1;
        int ans = list.size();
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (list.get(mid) >= target) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    static class Pair {
        int x;
        int index;

        public Pair(int x, int index) {
            this.x = x;
            this.index = index;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2250: Count Number of Rectangles Containing Each Point - Detailed explanation and solution approaches.

Topics

Array Hash Table Binary Search Binary Indexed Tree Sorting

Stats

Difficulty:Medium

Languages:4

Problem #:2250

Problem Explanation

🧭

Next Steps

Use this problem as a starting point, then move into adjacent patterns and company sets to reinforce the same idea in different contexts.

Topic hub

Study neighboring problems by pattern and difficulty.

Company hub

See where this problem appears in interview loops.

Pattern guides

Read deeper walkthroughs of the algorithm family.

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Create a list of lists, `rects_by_height`, to store rectangles grouped by their heights. Iterate through the `rectangles` array, placing the length of each rectangle into the list corresponding to its height.
2
Step 2: Sort the lengths of the rectangles within each height's list in `rects_by_height` in ascending order.
3
Step 3: Create a list of lists, `points_by_y`, to store points grouped by their y-coordinates. Store each point's x-coordinate and its original index within the points array.
4
Step 4: Initialize the `ans` array, which will store the result for each point.
5
Step 5: Initialize lengths_so_far, which store the rectangle lengths from heights greater than or equal to current height, in sorted order.
6
Step 6: Iterate through the heights from 100 down to 1. For each height:
7
Step 7: Merge new_lengths (rects at current height) with lengths_so_far into lengths_so_far maintaining sorted order
8
Step 8: Iterate through the points with y-coordinate equal to the current height. For each point, use binary search in lengths_so_far to find the index of the first length that is greater than or equal to the point's x-coordinate.
9
Step 9: The number of rectangles containing the point is the number of lengths in lengths_so_far that are greater than or equal to the point's x-coordinate, which is the length of lengths_so_far minus the index found in the previous step. Store this value in the `ans` array at the original index of the point.
10
Step 10: Return the `ans` array.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n + m*log(m) + p*m)

💾

Space Complexity

O(m + p)

📝

Why?

The time complexity is dominated by the sorting of rectangle lengths and binary searches. Creating `rects_by_height` and `points_by_y` takes O(m + p). Sorting the lengths at each height takes O(Sum(k_i log k_i)) which is less than O(m log m). Then, for each height, we merge current lengths with `lengths_so_far`, which grows with the sorted lengths. Inside the inner loop which iterates over heights descending from 100 to 1, each point has a binary search on `lengths_so_far`. So the total time is O(m log m + m + p + Sum(p_i * log m)) where sum is over each height. Space complexity is dominated by storing rectangles by height and points by y.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through each point and, for each point, iterate through all rectangles to check if the point is contained within the rectangle. Increment the count if the point is contained.

Time: O(m*p), where m is the number of rectangles and p is the number of points.Space: O(p), to store the result array.

Trade-offs: This approach is simple to implement but less efficient, especially when m and p are large. The main solution is better because it is more efficient, using sorting and binary search for optimizations. Brute force is only preferable for very small input sizes where the overhead of sorting and grouping might outweigh the benefits.

Using a 2D Segment Tree

Construct a 2D segment tree to represent the rectangles. Queries can then be made to determine how many rectangles contain each point.

Time: O(m*log(L)*log(H) + p*log(L)*log(H)), where L is the maximum length and H is the maximum height.Space: O(L*H)

Trade-offs: This approach can be more efficient than the brute force approach for very large datasets and can potentially handle updates to the rectangles efficiently. However, the implementation is significantly more complex, and the constant factors might make it slower for the constraints given in this problem. Also, the O(L*H) space complexity can become a bottleneck given large L and H.

✨

Key Insights

1Insight 1: Sorting rectangles by height and using binary search can efficiently determine how many rectangles contain a point.
2Insight 2: Processing points and rectangles by height, from highest to lowest, enables us to maintain a sorted list of rectangle lengths encountered so far, and quickly query how many of them contain a given point's x-coordinate.
3Insight 3: The height constraint (1 <= h_i, y_j <= 100) allows for the use of bucket sort (or counting sort) for grouping rectangles and points by their y-coordinates which improves performance.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty `rectangles` or `points` array. The code correctly handles these cases as the loops will simply not execute or will be skipped.
Edge case 2: A point lying exactly on the edge of a rectangle. The problem statement specifies that points on the edges are considered contained, and the solution correctly implements this condition.
Edge case 3: All points have the same y-coordinate. The code will still function correctly as the `lengths_so_far` array will be populated correctly before processing the points.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to sort the lengths of rectangles for each height before performing binary search. Binary search requires sorted data to function correctly.

✗Common mistake 2: Not handling the edge case where a point lies on the edge of a rectangle. The comparison should be inclusive (<=) and not exclusive (<).

✗Common mistake 3: Not initializing the result array `ans` correctly before iterating through the points.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: In databases, this algorithm can be used to efficiently query the number of geographical regions (rectangles) containing specific locations (points).

🏦Real-world scenario 2: In computer graphics, it can be applied to determine which objects (represented as rectangles) are visible from certain camera positions (points).

🎮Real-world scenario 3: In advertising, determining how many users (points based on demographics) fall into specific target audiences (rectangles based on interests, geography etc.).

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 30, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 21

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

What are the trade-offs of using a hash table?

What techniques are commonly tested in medium-difficulty problems?

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Count Number of Rectangles Containing Each Point"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?