Tap here to switch tabs
Problem
Submissions

Problem: Count Number of Rectangles Containing Each Point

med
30 min
Try to solve the Count Number of Rectangles Containing Each Point problem.

Statement

You are given a 22D integer array rectangles where rectangles[i] = [l_i, h_i] indicates that the iextthi^{ ext{th}} rectangle has a bottom left corner at (0,0)(0, 0) and a top right corner at (li,hi)(l_i, h_i).

You are also given a 22D integer array points where points[j] = [x_j, y_j] is a coordinate on the Cartesian plane.

The iextthi^{ ext{th}} rectangle contains the jextthj^{ ext{th}} point if 0≤xj≤li0 \leq x_j \leq l_i and 0≤yj≤hi0 \leq y_j \leq h_i.

Return an integer array ans of length equal to points.length, where ans[j] is the number of rectangles that contain the jextthj^{ ext{th}} point.

Note: A point that lies on the boundary of a rectangle is considered to be contained within the rectangle.

Constraints:

  • 1≤1 \leq rectangles.length, points.length ≤5imes104\leq 5 imes 10^4

  • rectangles[i].length ==== points[j].length ==2== 2

  • 1≤li,xj≤1091 \leq l_i, x_j \leq 10^9

  • 1≤hi,yj≤1001 \leq h_i, y_j \leq 100

  • All the rectangles are unique.

  • All the points are unique.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Number of Rectangles Containing Each Point

med
30 min
Try to solve the Count Number of Rectangles Containing Each Point problem.

Statement

You are given a 22D integer array rectangles where rectangles[i] = [l_i, h_i] indicates that the iextthi^{ ext{th}} rectangle has a bottom left corner at (0,0)(0, 0) and a top right corner at (li,hi)(l_i, h_i).

You are also given a 22D integer array points where points[j] = [x_j, y_j] is a coordinate on the Cartesian plane.

The iextthi^{ ext{th}} rectangle contains the jextthj^{ ext{th}} point if 0≤xj≤li0 \leq x_j \leq l_i and 0≤yj≤hi0 \leq y_j \leq h_i.

Return an integer array ans of length equal to points.length, where ans[j] is the number of rectangles that contain the jextthj^{ ext{th}} point.

Note: A point that lies on the boundary of a rectangle is considered to be contained within the rectangle.

Constraints:

  • 1≤1 \leq rectangles.length, points.length ≤5imes104\leq 5 imes 10^4

  • rectangles[i].length ==== points[j].length ==2== 2

  • 1≤li,xj≤1091 \leq l_i, x_j \leq 10^9

  • 1≤hi,yj≤1001 \leq h_i, y_j \leq 100

  • All the rectangles are unique.

  • All the points are unique.