You are given a stream of points on the X-Y plane. Design a data structure that supports adding new points and counting the number of axis-aligned squares that can be formed using a given query point as one corner.
add(point) — adds a point to the data structurecount(point) — returns the number of axis-aligned squares with the query as a corneradd([3,10]), add([11,2]), add([3,2])Constraints: 1 ≤ point.length == 2 · 0 ≤ x, y ≤ 1000 · At most 3000 calls total
Imagine you have a bag of points scattered on a grid. Someone hands you a new point and asks: “How many axis-aligned squares can you form using this point as a corner?” Your first instinct might be to check every possible triple of other points — but with 3000 points, that is O(n^3) per query. There has to be a better decomposition.
Imagine 3000 points on the grid. That triple-check means 27 billion candidate triples per query — and the problem allows 3000 queries. The grid has stored points and a query point. Which stored points could be part of a square with the query? There has to be a way to narrow the search dramatically.
Here is a grid of points and a query at (3, 3). Your job: figure out which stored points could be the OPPOSITE corner of a square — the corner diagonally across. What property must that opposite corner have?
Look at the grid above. For query (3, 3), some stored points could be the diagonal corner of a square. A diagonal corner is the one directly opposite — it shares NEITHER its x nor its y with the query. Can you spot which points qualify?