#2013 Detect Squares
the problem
In plain words
Points arrive one at a time on a grid. add(point) stores the point [x, y]; adding the same point again stores another copy, and copies count as different points. count(point) returns how many ways you can choose three stored points that make, together with the query point, a square with sides parallel to the axes and an area above zero.
in add([3,10]), add([11,2]), add([3,2]), count([11,10]), count([14,8]), add([11,2]), count([11,10])
out null, null, null, 1, 0, null, 2
With (11,10), the points (3,10), (3,2) and (11,2) make a square of side 8. A second copy of (11,2) gives a second choice for that corner.
- 0 ≤ x, y ≤ 1000
- At most 3000 calls to add and count in total
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFrequency countingHash lookup (seen before?)
A square through the query (x, y) has a corner in the same column, (x, y2). That fixes the side d = y2 − y, and the other two corners are (x ± d, y) and (x ± d, y2). Store counts of points, loop over the query's column, and multiply the counts of the three corners.
solutions
From brute force to optimal
For every stored point that could be the opposite corner, count the other two corners by scanning the list again.
- add: append a copy of the point.
- count: for each stored d with |d.x − x| == |d.y − y| > 0, count the stored points equal to (x, d.y) and to (d.x, y); add their product.
n candidate corners, each with a full scan of the n stored points.
Every copy is stored.
// On LeetCode, name this class DetectSquares.class DetectSquaresList { private final List<int[]> points = new ArrayList<>(); // every added point, duplicates included public void add(int[] point) { points.add(new int[] {point[0], point[1]}); } public int count(int[] point) { int x = point[0], y = point[1], ways = 0; for (int[] d : points) { // d = the corner diagonally opposite the query if (d[0] == x || Math.abs(d[0] - x) != Math.abs(d[1] - y)) continue; // not a square's diagonal int a = 0, b = 0; for (int[] p : points) { // count the other two corners by scanning again: O(n) each if (p[0] == x && p[1] == d[1]) a++; if (p[0] == d[0] && p[1] == y) b++; } ways += a * b; } return ways; }}cnt[x][y] counts copies; a list holds each different point once.
- add:
cnt[x][y]++; if it was 0, also add the point to the distinct list. - count: for each distinct d on a diagonal of the query, add cnt[d] × cnt[x][d.y] × cnt[d.x][y].
D = number of different points, up to min(n, 1001²).
The grid is about 10⁶ ints (≈ 4 MB) no matter how few points you store.
// On LeetCode, name this class DetectSquares.class DetectSquaresGrid { private final int[][] cnt = new int[1001][1001]; // cnt[x][y] = copies of (x, y); 0 ≤ x, y ≤ 1000 private final List<int[]> distinct = new ArrayList<>(); // each different point once public void add(int[] point) { if (cnt[point[0]][point[1]]++ == 0) distinct.add(new int[] {point[0], point[1]}); } public int count(int[] point) { int x = point[0], y = point[1], ways = 0; for (int[] d : distinct) { // every possible opposite corner: O(distinct points) if (d[0] == x || Math.abs(d[0] - x) != Math.abs(d[1] - y)) continue; ways += cnt[d[0]][d[1]] * cnt[x][d[1]] * cnt[d[0]][y]; // copies multiply } return ways; }}Only points in the query's column can be its vertical neighbour; each one fixes the side and two possible squares.
- add:
byX.computeIfAbsent(x, k -> new HashMap<>()).merge(y, 1, Integer::sum). - count: for each (y2, c) in column x with y2 ≠ y, side = y2 − y.
- For x2 in {x − side, x + side}: ways += c × copies(x2, y) × copies(x2, y2).
c = different y values in the query's column — at most 1,001 because 0 ≤ y ≤ 1000 — each with two pairs of map lookups.
One map entry per different point.
class DetectSquares { private final Map<Integer, Map<Integer, Integer>> byX = new HashMap<>(); // x → (y → copies of (x, y)) public void add(int[] point) { byX.computeIfAbsent(point[0], k -> new HashMap<>()).merge(point[1], 1, Integer::sum); } private int copies(int x, int y) { Map<Integer, Integer> column = byX.get(x); return column == null ? 0 : column.getOrDefault(y, 0); } public int count(int[] point) { int x = point[0], y = point[1], ways = 0; Map<Integer, Integer> column = byX.get(x); // a corner must share the query's x if (column == null) return 0; for (Map.Entry<Integer, Integer> e : column.entrySet()) { // at most 1,001 different y values int side = e.getKey() - y; if (side == 0) continue; // the same spot: a square needs positive area for (int x2 : new int[] {x - side, x + side}) { // the square on the left and on the right ways += e.getValue() * copies(x2, y) * copies(x2, e.getKey()); } } return ways; }}in the room
How to say it in the interview
talk track
- Clarify: sides parallel to the axes, copies count separately, area must be positive.
- Say the key step: the query is one corner; a second corner in its column fixes the whole square — on the left or on the right.
- Store counts, not copies: a corner with k copies multiplies the answer by k.
- Give the cost: count is O(points in one column) ≤ 1,001, however many points were added.
traps
- Counting zero-area "squares" when y2 == y — skip them.
- Treating copies as one point: the counts must multiply.
- Checking only the square on the right (x + side) — the one on the left (x − side) counts too.
- Accepting a rectangle: the horizontal side must equal the vertical side.
what they ask next
Follow-ups
Rectangles instead of squares?
The two sides are no longer tied. For each point in the query's column and each point in its row, look up the fourth corner. Cost: O(column size × row size) per count.
Points can also be removed?
Decrease the count (and drop the entry when it reaches 0). Nothing else changes — storing counts makes deletes trivial.
before you submit
Edge cases to test
- count before any add returns 0.
- Duplicate points multiply the number of ways.
- Copies of the query point itself never form a square with it (zero area).
- Squares on both sides of the query's column are both counted.
practise next
Similar problems
- #149Max Points on a LineHardin Math & Numbers
- #1Two SumEasyin Hashing
- #380Insert Delete GetRandom O(1)Mediumin Design DS