Detect Squares

Detect Squares is a design question. You build a small data structure that keeps taking points. Then it can quickly count how many squares it can form with a query point. The interviewer wants to see if you can pick the right structure so the counting stays fast.

🎯 The Problem

You build an object with two actions that work on a stream of points.

An axis-aligned square is a square whose sides are parallel to the grid lines. So no tilted squares. Each side is straight up or straight across.

The rules:

• add puts a point on the grid. The same point can be added many times.
• count takes a query point. It returns how many axis-aligned squares form using that query point and three points already added.
• A square needs four corners. One is the query. The other three come from added points.
• The same point added many times counts many times.

Let us add the points (3, 10), (11, 2), and (3, 2). Then we query the point (11, 10). These four points form one square with side length 8. So the count is 1.

add (3, 10)
add (11, 2)
add (3, 2)
count (11, 10)  -> 1

Explanation:
The four corners (3,10), (11,10), (11,2), (3,2)
form one axis-aligned square of side 8.

Here are the four corners of that one square on the grid.

🐢 Approach 1: Try Every Triple (Brute Force)

The idea:

• Store every added point in a list.
• For a query, try every group of three stored points.
• Check if those three plus the query form a square. Count the ones that work.

Why it is weak:

• The number of groups of three grows very fast as points pile up.
• Checking every triple per query is far too much work.
• This times out on a real test.

Here is the try-every-triple code:

class DetectSquares:
    def __init__(self):
        self.points = []

    def add(self, point):
        self.points.append(tuple(point))

    def count(self, point):
        x, y = point
        answer = 0
        for x1, y1 in self.points:
            for x2, y2 in self.points:
                for x3, y3 in self.points:
                    if (x1, y1) == (x, y):
                        continue
                    xs = sorted([x, x1, x2, x3])
                    ys = sorted([y, y1, y2, y3])
                    if xs[0] == xs[1] and xs[2] == xs[3] and ys[0] == ys[1] and ys[2] == ys[3] and xs[0] != xs[2] and ys[0] != ys[2]:
                        answer += 1
        return answer

⚡ Approach 2: Pick the Diagonal, Count With a Hash Map (Best)

The idea in one line: loop over candidate diagonal corners only, and once a diagonal is fixed the other two corners are forced.

The setup:

• Keep a hash map from each point to how many times it was added.
• A hash map stores a key and a value and looks up the key almost instantly.
• The key is the point. The value is its count.
• Also keep a list of distinct points to loop over.

How it works:

• Call the query point (qx, qy).
• Loop over each distinct stored point (px, py).
• Keep only points where the horizontal gap equals the vertical gap, both nonzero. That is a real diagonal corner.
• The other two corners are then forced: (qx, py) and (px, qy).
• Multiply the three corner counts. Add that product to the total.

Why it is fast:

• Each query loops over the distinct points once.
• The other corners are instant map lookups.
• So each query is O(n), linear in the number of distinct points.

This is the operation log for the example, showing the counts grow then the query.

Steps to Solve

1. Keep a hash map from each point to its count.
2. On add, increase the count for that point by one.
3. On count, start a total at zero.
4. Loop over every distinct stored point. Skip points on the same row or same column as the query.
5. Keep only points where the horizontal gap equals the vertical gap. That is a diagonal corner.
6. Multiply the counts of the diagonal point, (qx, py), and (px, qy). Add that product to the total.
7. Return the total.

#include <stdio.h>

int xs[100], ys[100], cnt[100];
int total = 0;  // number of distinct points stored

int getCount(int x, int y) {
    for (int i = 0; i < total; i++)
        if (xs[i] == x && ys[i] == y) return cnt[i];
    return 0;
}

void add(int x, int y) {
    for (int i = 0; i < total; i++) {
        if (xs[i] == x && ys[i] == y) { cnt[i]++; return; }
    }
    xs[total] = x; ys[total] = y; cnt[total] = 1; total++;
}

int countSquares(int qx, int qy) {
    int result = 0;
    for (int i = 0; i < total; i++) {
        int px = xs[i], py = ys[i];
        int dx = px - qx, dy = py - qy;
        // need a real diagonal: equal gaps, not same row or column
        if (dx != 0 && (dx == dy || dx == -dy)) {
            result += cnt[i] * getCount(qx, py) * getCount(px, qy);
        }
    }
    return result;
}

int main(void) {
    add(3, 10);
    add(11, 2);
    add(3, 2);
    printf("%d\n", countSquares(11, 10));
    return 0;
}

1

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

class DetectSquares {
    unordered_map<long long, int> counts;   // packed point -> count
    vector<pair<int,int>> points;            // distinct points

    long long key(int x, int y) { return (long long)x * 100000 + y; }
public:
    void add(int x, int y) {
        long long k = key(x, y);
        if (counts[k] == 0) points.push_back({x, y});
        counts[k]++;
    }
    int countSquares(int qx, int qy) {
        int result = 0;
        for (auto& p : points) {
            int px = p.first, py = p.second;
            int dx = px - qx, dy = py - qy;
            if (dx != 0 && (dx == dy || dx == -dy)) {
                result += counts[key(px, py)] * counts[key(qx, py)] * counts[key(px, qy)];
            }
        }
        return result;
    }
};

int main() {
    DetectSquares ds;
    ds.add(3, 10);
    ds.add(11, 2);
    ds.add(3, 2);
    cout << ds.countSquares(11, 10) << endl;
    return 0;
}

1

import java.util.*;

public class DetectSquares {
    private Map<Long, Integer> counts = new HashMap<>();
    private List<int[]> points = new ArrayList<>();

    private long key(int x, int y) { return (long) x * 100000 + y; }

    public void add(int x, int y) {
        long k = key(x, y);
        if (counts.getOrDefault(k, 0) == 0) points.add(new int[]{x, y});
        counts.put(k, counts.getOrDefault(k, 0) + 1);
    }

    public int countSquares(int qx, int qy) {
        int result = 0;
        for (int[] p : points) {
            int px = p[0], py = p[1];
            int dx = px - qx, dy = py - qy;
            if (dx != 0 && (dx == dy || dx == -dy)) {
                result += counts.getOrDefault(key(px, py), 0)
                        * counts.getOrDefault(key(qx, py), 0)
                        * counts.getOrDefault(key(px, qy), 0);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        DetectSquares ds = new DetectSquares();
        ds.add(3, 10);
        ds.add(11, 2);
        ds.add(3, 2);
        System.out.println(ds.countSquares(11, 10));
    }
}

1

class DetectSquares:
    def __init__(self):
        self.counts = {}   # (x, y) -> how many times added
        self.points = []   # list of distinct points

    def add(self, x, y):
        if (x, y) not in self.counts:
            self.points.append((x, y))
            self.counts[(x, y)] = 0
        self.counts[(x, y)] += 1

    def count(self, qx, qy):
        result = 0
        for px, py in self.points:
            dx = px - qx
            dy = py - qy
            # real diagonal: equal gaps, not same row or column
            if dx != 0 and (dx == dy or dx == -dy):
                result += (self.counts[(px, py)]
                           * self.counts.get((qx, py), 0)
                           * self.counts.get((px, qy), 0))
        return result


ds = DetectSquares()
ds.add(3, 10)
ds.add(11, 2)
ds.add(3, 2)
print(ds.count(11, 10))

1

class DetectSquares {
  constructor() {
    this.counts = new Map(); // "x,y" -> count
    this.points = [];        // distinct points
  }

  add(x, y) {
    const k = `${x},${y}`;
    if (!this.counts.has(k)) this.points.push([x, y]);
    this.counts.set(k, (this.counts.get(k) || 0) + 1);
  }

  count(qx, qy) {
    let result = 0;
    for (const [px, py] of this.points) {
      const dx = px - qx;
      const dy = py - qy;
      if (dx !== 0 && (dx === dy || dx === -dy)) {
        result += (this.counts.get(`${px},${py}`) || 0)
                * (this.counts.get(`${qx},${py}`) || 0)
                * (this.counts.get(`${px},${qy}`) || 0);
      }
    }
    return result;
  }
}

const ds = new DetectSquares();
ds.add(3, 10);
ds.add(11, 2);
ds.add(3, 2);
console.log(ds.count(11, 10));

1

Let us walk through the Python version line by line.

def add(self, x, y):
    if (x, y) not in self.counts:
        self.points.append((x, y))
        self.counts[(x, y)] = 0
    self.counts[(x, y)] += 1

The first time we see a point, we add it to the points list and set its count to zero. The list holds only distinct points, so the query loop never repeats work. Then we increase the count by one. So a point added three times has a count of three.

for px, py in self.points:
    dx = px - qx
    dy = py - qy

We loop over each distinct stored point. dx is the horizontal gap from the query to this point. dy is the vertical gap. These two gaps decide if this point can be a diagonal corner.

if dx != 0 and (dx == dy or dx == -dy):

This is the key test. dx != 0 throws out points on the same column as the query. It also rules out the same row, because if dx is zero the gaps cannot be equal and nonzero. The part dx == dy or dx == -dy means the horizontal gap and the vertical gap have the same size. Equal sides means a square. So this point sits on a real diagonal from the query.

result += (self.counts[(px, py)]
           * self.counts.get((qx, py), 0)
           * self.counts.get((px, qy), 0))

Once we have the diagonal point, the other two corners are fixed. They are (qx, py) and (px, qy). We multiply three counts. The diagonal point may itself have been added many times, and so may the side corners. The product counts every combination. We use .get(..., 0) so a missing corner contributes zero, not an error.

return result

After the loop, result holds the total number of squares for this query.

⏱️ Time and Space Complexity

The brute force checks every group of three points, which grows very fast and is far too slow. The hash map version loops over the distinct points once per query, so each query is O(n) where n is the number of distinct points. The add is O(1). The space is O(n) to hold the points and counts.

🧩 Key Takeaways

• ✅ Store each point with a count, because the same point can be added many times.
• ✅ For a query, loop over stored points and keep only true diagonal corners.
• ✅ A diagonal corner has an equal horizontal gap and vertical gap, both nonzero.
• ✅ Once the diagonal is fixed, the other two corners are forced, so just multiply three counts.
• ✅ This makes each query linear in the number of distinct points, not the number of triples.

🚀 What’s Next?

• Pow(x, n)
• Happy Number