LeetCode 2013 · Math & Geometry

Detect Squares, explained with a picture

Pegs on a board that form squares.

MediumMath & Geometry
▶ Watch it step by step

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 add operation and a count query, 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

  1. 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.
  2. The other two corners are determined. They are (x, qy) and (qx, y). There is nothing left to search for, only to look up.
  3. Store counts. A Counter maps each point to how many copies were added. add is one increment.
  4. 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.
  5. Skip the bad candidates. The test abs(x - qx) != abs(y - qy) or x == qx rejects 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 total

LeetCode 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

ApproachTimeSpace
Brute forceadd O(1), count O(n³): every group of three stored pointsO(n): the list
Counter (shown code)add O(1); count O(d), where d is the number of distinct stored pointsO(d): one entry per distinct point

Edge cases

  • Empty structure: count_squares returns 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: Counter returns 0 for a missing key without storing it, so lookups of (x, qy) never add entries. (With a defaultdict they would, and iterating over the dictionary directly would then raise a RuntimeError.)
  • 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 == qx test. 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.
Your turn: any rectangle

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.

Check what stuck

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?

2. Why is the shown count_squares fast enough for 3000 calls?

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)?

Score 60% or more and the lesson is marked complete.