Rectangles From Survey Markers
MediumMath & Geometry
Problem
Survey markers sit at distinct integer points points[i] = [x, y]. A plot can be fenced as a rectangle with sides parallel to the axes if all four of its corners have markers.
Return how many such rectangles (with positive width and height) can be formed.
Example 1
- Input:
- points = [[0, 0], [0, 2], [3, 0], [3, 2], [5, 0], [5, 2]]
- Output:
- 3
Columns x = 0, 3 and 5 all hold markers at y = 0 and y = 2, and any two of those columns make a rectangle.
Example 2
- Input:
- points = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
- Output:
- 1
Example 3
- Input:
- points = [[0, 0], [1, 1], [2, 2]]
- Output:
- 0
Constraints
- 1 ≤ points.length ≤ 1500
- -10^4 ≤ x, y ≤ 10^4
- All points are distinct
Hint
Show the first hint
A rectangle is fixed by its left column, its right column and a pair of y-values that both columns contain.
Walkthrough
How to approach it
01Clarify before coding
- Are the points distinct? Yes.
- Must sides be parallel to the axes? Yes; tilted rectangles do not count.
- Are degenerate rectangles (zero width or height) counted? No; distinct points guarantee positive sizes here.
02Brute force
Try every pair of points as opposite corners (x1, y1), (x2, y2) with x1 ≠ x2 and y1 ≠ y2, and check whether the other two corners exist in a hash set.
Cost: O(n²) with a set, then divide by 2 because each rectangle has two diagonals. Fine for this size, but easy to double count; the column method counts each rectangle exactly once.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.