The problem
Design a structure where you add points (repeats allowed) and, for a query point, count how many ways it can form an axis-aligned square (sides parallel to the axes, positive area) with three added points.
Input: add (2,8), add (8,2), add (2,2), count (8,8), count (9,7), add (8,2), count (8,8) Output: 1, 0, 2
Picture it
Picture pegs on a board. For a query point, try every peg that could be the opposite corner of a square (same distance in x and y, not zero). Then the other two corners are fixed, so we just look up how many pegs sit there. Multiply the counts, since repeated pegs make different squares.
How to recognise it
- You design a data structure with an
addoperation and acountquery, mixed in any order. - A query asks for combinations that satisfy a geometric rule: here, an axis-aligned square with the query as a corner.
- Once part of the shape is fixed, the remaining corners are fully determined, so a lookup finds them.
- Points can repeat, and each copy gives different squares, so you need counts, not just presence.
- Up to 3000 calls rule out checking every group of stored points on each query.
Start with brute force
Keep every added point in a list. For a query, try every group of three stored points and check whether, with the query point, they are the four corners of a square whose sides are parallel to the axes.
from itertools import combinations
def count_brute(points, q):
total = 0
for trio in combinations(points, 3): # repeats in the list count separately
four = list(trio) + [tuple(q)]
xs = {p[0] for p in four}
ys = {p[1] for p in four}
if (len(set(four)) == 4 and len(xs) == 2 and len(ys) == 2
and max(xs) - min(xs) == max(ys) - min(ys)):
total += 1
return total
With n stored points a query checks C(n, 3) groups. For n = 3000 that is about 4.5 × 10^9 groups, far too slow. Space is O(n) for the list.
From brute force to the idea
- Fix the diagonal. In a square with the query corner
(qx, qy), the opposite corner(x, y)is at the same distance in x and y:abs(x - qx) == abs(y - qy), and not zero, otherwise the area would be 0. - The other two corners are determined. They are
(x, qy)and(qx, y). There is nothing left to search for, only to look up. - Store counts. A
Countermaps each point to how many copies were added.addis one increment. - Multiply the counts. For each stored point that can be the opposite corner, the number of squares is
c * count[(x, qy)] * count[(qx, y)], because any copy of each corner combines with any copy of the others. Add this over all candidate diagonal points. - Skip the bad candidates. The test
abs(x - qx) != abs(y - qy) or x == qxrejects points that are not on a diagonal of the right size, and the point at distance zero.
This is the key idea: the diagonal point fixes the whole square, so each query becomes one pass over the stored distinct points with two dictionary lookups each.
The key idea
Count points in a dictionary; for each diagonal candidate, multiply the counts of the other two corners.
Python solution
class DetectSquares:
def __init__(self):
self.count = Counter() # (x, y) -> pegs there
def add(self, p):
self.count[tuple(p)] += 1
def count_squares(self, q):
qx, qy = q
total = 0
for (x, y), c in list(self.count.items()):
if abs(x - qx) != abs(y - qy) or x == qx:
continue # not a diagonal corner
total += c * self.count[(x, qy)] * self.count[(qx, y)]
return totalLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | add O(1), count O(n³): every group of three stored points | O(n): the list |
| Counter (shown code) | add O(1); count O(d), where d is the number of distinct stored points | O(d): one entry per distinct point |
Edge cases
- Empty structure:
count_squaresreturns 0. - Query point stored itself: the stored copy has
x == qx, so it is skipped and never counts as its own diagonal corner. With one point[1, 1]stored and query[1, 1]the answer is 0. - Duplicates multiply: after adding
[0,0]twice and[1,0]three times, plus[0,1]once, the query[1,1]returns 2 × 1 × 3 = 6. - Same row or column as the query: such points fail the diagonal test, so a flat shape never counts.
- Query does not change the data:
Counterreturns 0 for a missing key without storing it, so lookups of(x, qy)never add entries. (With adefaultdictthey would, and iterating over the dictionary directly would then raise aRuntimeError.) - Imports: the shown class needs
from collections import Counter.
Common mistakes
- Using a set of points instead of counts, which counts each square once. With points
[2,8],[8,2],[2,2],[8,2]and query[8,8]it returns 1 instead of 2. - Dropping the
x == qxtest. A stored copy of the query point then counts:[1,1]stored and query[1,1]returns 1. - Adding instead of multiplying the counts of the three corners.
Count the axis-aligned rectangles (any positive width and height, not only squares) that have the query point as a corner and three stored points as the other corners. After adding [0,0], [0,2], [3,0] and [3,0], the query [3,2] has 2 rectangles. Describe your approach, then write it if you like.
Compare with our answer
The same idea with a weaker test: any stored point that shares neither the row nor the column of the query can be the opposite corner. The other two corners are still determined.
from collections import Counter
class DetectRectangles:
def __init__(self):
self.count = Counter()
def add(self, p):
self.count[tuple(p)] += 1
def count_rectangles(self, q):
qx, qy = q
total = 0
for (x, y), c in list(self.count.items()):
if x == qx or y == qy: # same row or column: no area
continue
total += c * self.count[(x, qy)] * self.count[(qx, y)]
return total
The query [0, 0] after those points returns 0, and the query [1, 1] returns 0 as well. Time O(d) per query, space O(d).
A strong answer mentions: removing the equal-distance test, keeping the product of counts, and rejecting points in the query's own row or column.
1. You must support add(number) and count(target), where count is the number of pairs of stored numbers (different insertions) that sum to target, and numbers can repeat. Which idea carries over from the shown solution?
Once one number is chosen, the partner is determined, so a hash lookup replaces a search, and counts handle repeats (a value equal to its own partner needs care). A set would lose copies, and rebuilding pairs is far too slow.
2. Why is the shown count_squares fast enough for 3000 calls?
Each query costs O(d) lookups at most. It does not stop early, sort, or cache queries.
3. A learner removes or x == qx from the skip test. What does count_squares([1, 1]) return when only [1, 1] has been added (once)?
The stored point has the same distance (0) in x and y, so it passes the diagonal test, and its three counts are 1 × 1 × 1. Running the variant gives 1 where the correct code gives 0.
Score 60% or more and the lesson is marked complete.