#2013 Detect Squares

Problem

Design a data structure that supports adding points on a 2D plane and counting how many axis-aligned squares can be formed with a given query point.

An axis-aligned square is a square whose sides are parallel to the x-axis and y-axis (no tilted/rotated squares).

Implement the DetectSquares class:

DetectSquares() — Initializes with an empty data structure
void add(point) — Adds a new point [x, y]. Duplicates are allowed.
int count(point) — Counts the number of ways to choose three points from the data structure so that those three points plus the query point form an axis-aligned square with positive area

Input:
  ["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
  [[], [[3,10]], [[11,2]], [[3,2]], [[11,10]], [[14,8]], [[11,2]], [[11,10]]]

Output:
  [null, null, null, null, 1, 0, null, 2]

Constraints:

0 <= x, y <= 1000
At most 3000 total calls to add and count

Intuition

What does an axis-aligned square even look like?

Let's start from the very basics. An axis-aligned square has four corners, and its sides are perfectly horizontal and vertical — no tilting allowed.

(x1, y2) ─────── (x2, y2)
    |                 |
    |     square      |
    |                 |
(x1, y1) ─────── (x2, y1)

Notice something important: the four corners of any axis-aligned square can be described with just two x-values and two y-values. If you know any two diagonally opposite corners, the other two corners are fully determined.

What are we actually being asked?

When count([x1, y1]) is called, we're given one corner of a potential square. We need to find how many sets of 3 other points in our data structure complete a square with this query point.

Let's think about this step by step.

Step 1 — What defines a square? The diagonal.

Given our query point (x1, y1), if we can find a diagonal partner (x2, y2), the other two corners are automatically:

(x1, y2) and (x2, y1)

Let's see this visually. Say our query point is (11, 10):

(3, 10) ─────── (11, 10)  ← query point
    |                |
    |                |
(3,  2) ─────── (11,  2)

If (3, 2) is the diagonal partner, then the other two corners must be (3, 10) and (11, 2). No choice — they're locked in.

Step 2 — But wait, what makes a diagonal valid?

Not every pair of points forms a valid square diagonal. For an axis-aligned square, the diagonal must satisfy one rule: the side lengths must be equal. Since the sides are axis-aligned, the horizontal distance must equal the vertical distance:

|x2 - x1| must equal |y2 - y1|

And both must be greater than zero (the problem says "positive area" — a point by itself doesn't count as a square).

Step 3 — The counting approach

So here's our strategy for count(x1, y1):

Look at every point (x2, y2) we've stored that could be a diagonal partner
A valid diagonal means |x2 - x1| === |y2 - y1| and both are non-zero
For each valid diagonal, check if the other two corners (x1, y2) and (x2, y1) exist in our data
Since duplicates are allowed, multiply the counts: if (x1, y2) appears 3 times and (x2, y1) appears 2 times, that's 3 × 2 = 6 different squares

But iterating over every stored point for every query could be slow. Can we be smarter?

Step 4 — A cleaner approach: fix one side, not the diagonal

Instead of searching for diagonals, let's think differently. Let's look for points that share the same x-coordinate as our query point — points directly above or below it.

Why? Because if we find a point (x1, y2) — same x, different y — then we know the side length of the square: d = |y2 - y1|. And once we know the side length, the other two corners are determined:

Query: (x1, y1)
Found: (x1, y2)    ← same column, distance d = |y2 - y1|

The square extends horizontally by d, so the remaining corners are:
  (x1 + d, y1) and (x1 + d, y2)    ← square to the RIGHT
  or
  (x1 - d, y1) and (x1 - d, y2)    ← square to the LEFT

Let's draw this out:

d = y2 - y1

Case 1: square extends RIGHT          Case 2: square extends LEFT

(x1, y2) ──── (x1+d, y2)             (x1-d, y2) ──── (x1, y2)
    |              |                       |              |
    |              |                       |              |
(x1, y1) ──── (x1+d, y1)             (x1-d, y1) ──── (x1, y1)
   query                                              query

For each direction, we just check: do those two corner points exist in our data?

Step 5 — Putting it all together

Here's the refined plan:

add(x, y): Store the point count in a hash map. We need to quickly look up "how many times has point (x, y) been added?" and also "what are all the points with x-coordinate equal to some value?"

count(x1, y1):

Look at every point (x1, y2) that shares the same x-coordinate as the query (same column)
Skip if y2 === y1 (zero side length = no area)
The side length is d = y2 - y1 (we keep the sign to handle both directions)
The other two corners would be at (x1 + d, y1) and (x1 + d, y2)
Multiply the counts of all three points: count(x1, y2) × count(x1 + d, y1) × count(x1 + d, y2)
Sum across all possible y2 values and add d going left too: (x1 - d, y1) and (x1 - d, y2)

Actually, there's an even simpler way to think about step 4-6. Instead of separately handling left and right, notice that d = y2 - y1 can be positive or negative. If we use d directly (not |d|), then checking (x1 + d, ...) already handles both directions as y2 ranges above and below y1.

Wait — let me reconsider. The side length is |y2 - y1|, and the square can go left or right. Let me be more explicit:

For each (x1, y2) in the same column:

sideLen = y2 - y1 (could be positive or negative, doesn't matter)
Check right: corners at (x1 + sideLen, y1) and (x1 + sideLen, y2)
Check left: corners at (x1 - sideLen, y1) and (x1 - sideLen, y2)

Hmm, but this double counts... Let me think again.

Step 5 (revised) — The simplest correct approach

Actually, the cleanest way is to not fix a column but instead iterate over all diagonal candidates directly. For each point (x2, y2) in our data:

Check |x2 - x1| === |y2 - y1| and both non-zero (valid diagonal)
The other two corners are (x1, y2) and (x2, y1)
Add count(x1, y2) × count(x2, y1) to the result

But we'd iterate over potentially many points. Let's go back to the column approach done correctly.

The trick: iterate over points (x2, y2) that are diagonal to the query. Since we need |x2 - x1| = |y2 - y1|, and we want to iterate efficiently, we fix the y-coordinate by looking at all points that share the query's x-coordinate, then compute the x-offset.

Here's the clearest version:

For each (x1, y2) in the same column as the query (same x):

d = abs(y2 - y1) — this is the side length
If d === 0, skip (no area)
The diagonal point is either (x1 + d, y2) or (x1 - d, y2)
For the right square: other corners are (x1 + d, y1) and (x1 + d, y2) → add count(x1 + d, y1) × count(x1 + d, y2)
For the left square: other corners are (x1 - d, y1) and (x1 - d, y2) → add count(x1 - d, y1) × count(x1 - d, y2)

And we multiply by the count of (x1, y2) itself since duplicates matter.

Why multiply counts?

This is a subtle but important point. If point (3, 10) has been added 2 times and point (3, 2) has been added 3 times, how many different squares can they participate in?

Each copy of (3, 10) can pair with each copy of (3, 2). That's 2 × 3 = 6 combinations. Multiplying counts handles duplicates naturally.

What data structures do we need?

pointCount — A map from "x,y" to its count: how many times has this exact point been added?
xToYs — A map from x to a list of all y-values added at that x-coordinate (including duplicates, but we'll use pointCount for the actual counts)

Actually, we just need xToYs to know which y-values exist at a given x. We don't need duplicates in the list if we track counts separately. So xToYs[x] is a Set of y-values, and pointCount["x,y"] is the count.

Walkthrough of the example

Let's trace through the example step by step:

add([3, 10])  → pointCount: {(3,10):1}
add([11, 2])  → pointCount: {(3,10):1, (11,2):1}
add([3, 2])   → pointCount: {(3,10):1, (11,2):1, (3,2):1}

count([11, 10]) — query point is (11, 10)

Look at all points with x = 11: we have (11, 2).

(x1, y1) = (11, 10)    query
(x1, y2) = (11, 2)     same column
d = |10 - 2| = 8

Right square (x1 + d = 19):
  Need (19, 10) and (19, 2) → neither exists → 0

Left square (x1 - d = 3):
  Need (3, 10) and (3, 2) → both exist with count 1!
  Contribution: count(11,2) × count(3,10) × count(3,2)
               = 1 × 1 × 1 = 1

Let's verify visually:

(3, 10) ─────── (11, 10)  ← query
    |                |
    |    8 × 8       |
    |                |
(3,  2) ─────── (11,  2)

All four corners exist. Result: 1 ✓

count([14, 8]) — query point is (14, 8)

Look at all points with x = 14: none exist. Result: 0 ✓

add([11, 2])  → pointCount: {(3,10):1, (11,2):2, (3,2):1}

count([11, 10]) again — query point is (11, 10)

Same column search: (11, 2) with count 2 now.

Left square (x1 - d = 3):
  count(11,2) × count(3,10) × count(3,2)
  = 2 × 1 × 1 = 2

The duplicate (11, 2) creates a second square because each copy is treated as a distinct point. Result: 2 ✓

Solution

class DetectSquares {
  constructor() {
    // pointCount["x,y"] = number of times point (x,y) has been added
    this.pointCount = new Map();
    // xToYs[x] = Set of all y-values that have been added with this x
    this.xToYs = new Map();
  }
 
  add(point) {
    const [x, y] = point;
    const key = `${x},${y}`;
    this.pointCount.set(key, (this.pointCount.get(key) || 0) + 1);
 
    if (!this.xToYs.has(x)) {
      this.xToYs.set(x, new Set());
    }
    this.xToYs.get(x).add(y);
  }
 
  count(point) {
    const [x1, y1] = point;
    let result = 0;
 
    // Look at all points in the same column as the query
    const ys = this.xToYs.get(x1);
    if (!ys) return 0;
 
    for (const y2 of ys) {
      const d = Math.abs(y2 - y1);
      if (d === 0) continue; // need positive area
 
      const countSameCol = this.pointCount.get(`${x1},${y2}`) || 0;
 
      // Try square extending to the RIGHT (x1 + d)
      const rightTop = this.pointCount.get(`${x1 + d},${y1}`) || 0;
      const rightDiag = this.pointCount.get(`${x1 + d},${y2}`) || 0;
      result += countSameCol * rightTop * rightDiag;
 
      // Try square extending to the LEFT (x1 - d)
      const leftTop = this.pointCount.get(`${x1 - d},${y1}`) || 0;
      const leftDiag = this.pointCount.get(`${x1 - d},${y2}`) || 0;
      result += countSameCol * leftTop * leftDiag;
    }
 
    return result;
  }
}

Line-by-line breakdown

Constructor (lines 2-6) — Two data structures. pointCount is the core: a map from "x,y" strings to how many times that point has been added. xToYs is a helper: for each x-coordinate, it stores the set of y-coordinates we've seen. This lets us quickly find "all points in the same column."

add (lines 8-15) — Increment the count for this point. Also register the y-value under this x-coordinate in our column lookup.

count (lines 17-38) — The main logic:

Line 21-22: Get all y-values that share x1. If there are none, no squares are possible.
Line 24-25: For each y-value y2 in that column, compute the side length d. Skip if zero.
Line 27: Get how many copies of the column-mate (x1, y2) exist.
Lines 29-31: Check the right square. Look up (x1+d, y1) and (x1+d, y2). Multiply all three counts.
Lines 33-36: Check the left square. Same idea, but using x1-d.
Line 38: Return the accumulated total.

Why do we check both left and right?

Given the query (x1, y1) and a column-mate (x1, y2), the square could extend in either direction:

LEFT                                RIGHT

(x1-d, y2) ── (x1, y2)            (x1, y2) ── (x1+d, y2)
     |            |                    |            |
(x1-d, y1) ── (x1, y1)            (x1, y1) ── (x1+d, y1)
                query               query

Both are valid axis-aligned squares with the same side length. We count them separately.

Why use a string key like `"x,y"`?

JavaScript Maps use reference equality for objects, so new Map().set([3,10], 1) wouldn't let you look up [3,10] later with a different array. String keys like "3,10" solve this because strings compare by value.

Walking through a more complex example

Let's trace a scenario with duplicate points and multiple squares:

add([0, 0])
add([0, 2])
add([2, 0])
add([2, 2])
add([0, 0])    ← duplicate!
add([2, 0])    ← duplicate!

State: (0,0):2, (0,2):1, (2,0):2, (2,2):1

count([0, 2]) — query is (0, 2)

Column x=0 has y-values: {0, 2}

y2 = 0: d = |2 - 0| = 2
  countSameCol = count(0,0) = 2

  Right (x=2): count(2,2) × count(2,0) = 1 × 2 = 2
  Contribution: 2 × 2 = 4

  Left (x=-2): count(-2,2) × count(-2,0) = 0 × 0 = 0
  Contribution: 2 × 0 = 0

y2 = 2: d = 0, skip

Result: 4

Why 4? Let's name the duplicate points:

(0,0)_A and (0,0)_B are at the bottom-left
(2,0)_A and (2,0)_B are at the bottom-right

The four squares use the query (0,2) and (2,2) as the top corners, with these bottom-corner combinations:

Square 1: (0,0)_A, (2,0)_A
Square 2: (0,0)_A, (2,0)_B
Square 3: (0,0)_B, (2,0)_A
Square 4: (0,0)_B, (2,0)_B

That's 2 × 2 = 4. The multiplication naturally accounts for duplicates. ✓

Why not iterate over all diagonal points?

An alternative approach iterates over every stored point as a potential diagonal. This works but is less efficient:

// Alternative: iterate all points as diagonal candidates
count(point) {
  const [x1, y1] = point;
  let result = 0;
 
  for (const [key, diagCount] of this.pointCount) {
    const [x2, y2] = key.split(',').map(Number);
    if (Math.abs(x2 - x1) !== Math.abs(y2 - y1)) continue;
    if (x2 === x1) continue; // same column = zero area
 
    const c1 = this.pointCount.get(`${x1},${y2}`) || 0;
    const c2 = this.pointCount.get(`${x2},${y1}`) || 0;
    result += diagCount * c1 * c2;
  }
 
  return result;
}

This iterates over all distinct points in the data structure for every query. Our column-based approach only iterates over points sharing the query's x-coordinate, which is usually much fewer.

Complexity

Time:
- add: O(1) — hash map insertion
- count: O(n) in the worst case, where n is the number of distinct y-values at the query's x-coordinate. In practice, this is much smaller than the total number of points.
Space: O(n) — where n is the total number of distinct points stored

Common mistakes

Forgetting duplicates — The problem says duplicate points are allowed and treated as distinct. If you only store presence (boolean), you'll miss counting all combinations. You must track counts.
Not checking both directions — A square can extend left or right from the column. Only checking one direction misses valid squares.
Counting zero-area "squares" — If y2 === y1, the "square" has zero side length. The problem requires positive area, so skip these.
Using arrays as map keys — In JavaScript, [3, 10] !== [3, 10] (different references). Use string keys or a nested map structure.

Key Takeaway

When a problem asks you to detect geometric shapes from a collection of points, think about which parts of the shape you can fix and which parts are determined. Here, fixing one side of the square (the vertical side via a column-mate) determines the side length, which determines where the other two corners must be. This turns a geometric search into hash map lookups — from "search everywhere" to "look up exactly what you need."