Detect Squares

The problem

A store collects grid points and counts squares. operations names the operations to run, in order, and values holds the arguments of each. "DetectSquares" comes first, has no arguments and creates the empty store. "add" has a point, x then y, and stores it; a point added again is stored again. "count" has a query point and asks in how many ways three stored points can be chosen that form a square with that point, with sides parallel to the axes and longer than 0. Copies of a point are separate choices. Return one result per operation, in a list: the number for each "count", null for every other operation.

What to write

function solve(operations: string[], values: number[][]): (number | null)[]

Input
operations = ["DetectSquares","add","add","add","count","count","add","count"]
values = [[],[3,10],[11,2],[3,2],[11,10],[14,8],[11,2],[11,10]]

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

Input
operations = ["DetectSquares","count"]
values = [[],[0,0]]

Output
[null,0]

Constraints

Return null for construction and add.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A point can be added several times, and each copy is a separate choice. So knowing whether a point is stored is not enough: you need how many copies there are. The sides are parallel to the axes, so the corners of one square use only two different x values and two different y values.

2. Hint 2: Ask a smaller question

   The query point is (11, 10), and you decide that the corner diagonally across from it is (3, 2). Where must the other two corners be? Could (3, 5) have been the corner diagonally across instead?

3. Hint 3: Name the pattern

   You are asked to build a store with its own operations, and no ready-made container answers a count. So design one: a hash map from each point to its number of copies. For a count, every stored point diagonal to the query fixes the other two corners, and two lookups give their copies. This is a purpose-built data structure. Read the lesson on purpose-built data structure.

4. Hint 4: State the invariant

   The map holds, for every point added so far, its exact number of copies. Each square that has the query point as a corner has exactly one corner diagonally opposite. So going through the stored points as opposite corners meets every square position once, and the copies of its three corners multiply.

5. Hint 5: Sketch the pseudocode

   add: raise the point's count by 1. count at (x, y): total = 0. For each stored point (a, b) with c copies, skip it if a = x, or if its sideways and up-down distances to the query differ. Otherwise total += c × copies of (x, b) × copies of (a, y), missing points counting 0. Result: total.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Enumerate stored opposite corners whose horizontal and vertical distances match, then multiply the occurrence counts at the other two corners.

The slow way

Keep every added point in a list. For a count, try every choice of three stored points and test whether they form a square with the query point. It is correct, but n stored points give about n × n × n / 6 choices, and that work is repeated for every count.

The insight

A square with sides parallel to the axes is decided by two opposite corners: the other two corners are forced. So a count has only one thing to choose, the corner opposite the query point. For each stored point that can be that corner, look up how many copies of the two forced corners exist, and multiply.

Step by step

1. Keep a count for every point that has been added. The same point can be added several times, and each copy is a separate choice. A hash map from point to number of copies answers "how many of this point are stored?" in about one step.
2. Handle the operations in order and give one result for each. The answer is a list with one entry per operation, in the same order. Only a count produces a number. Creating the store and adding a point give null.
3. An add raises the count of its point by one. A point seen for the first time starts from 0, so its count becomes 1. A point added again gets a higher count, not a second entry in the map.
4. A count tries every stored point as the opposite corner. Every square with the query point as a corner has exactly one corner diagonally across from it. Trying each different stored point in that role reaches every possible square once.
5. Skip a point that is not diagonal to the query point. Opposite corners of a square are equally far apart sideways and up and down, and never in the same column. Distances are compared without their signs, as absolute values, so the corner may lie in any diagonal direction.
6. The other two corners are fixed: multiply the three counts. One of them has the query's x and the opposite corner's y; the second has the reverse. Any copy of one corner goes with any copy of the others, so the counts multiply. A missing corner counts as 0.

The same numbered steps are the comments in each solution.

function solve(operations, values) {
    // 1. Keep a count for every point that has been added
    const points = new Map();
    // 2. Handle the operations in order and give one result for each
    return operations.map((op, i) => {
        // "DetectSquares" only creates the empty store, so it has no result.
        if (op === "DetectSquares")
            return null;
        const [x, y] = values[i];
        if (op === "add") {
            // 3. An add raises the count of its point by one
            // A Map does not treat two arrays with the same numbers as the same
            // key, so a point is stored under the text "x,y".
            const key = x + "," + y;
            points.set(key, (points.get(key) || 0) + 1);
            return null;
        }
        // 4. A count tries every stored point as the opposite corner
        let total = 0;
        for (const [key, count] of points) {
            const [a, b] = key.split(",").map(Number);
            // 5. Skip a point that is not diagonal to the query point
            if (a === x || Math.abs(a - x) !== Math.abs(b - y))
                continue;
            // 6. The other two corners are fixed: multiply the three counts
            total +=
                count * (points.get(x + "," + b) || 0) * (points.get(a + "," + y) || 0);
        }
        return total;
    });
}

function solve(operations: string[], values: number[][]): (number | null)[] {
  // 1. Keep a count for every point that has been added
  const points = new Map<string, number>();
  // 2. Handle the operations in order and give one result for each
  return operations.map((op, i) => {
    // "DetectSquares" only creates the empty store, so it has no result.
    if (op === "DetectSquares") return null;
    const [x, y] = values[i];
    if (op === "add") {
      // 3. An add raises the count of its point by one
      // A Map does not treat two arrays with the same numbers as the same
      // key, so a point is stored under the text "x,y".
      const key = x + "," + y;
      points.set(key, (points.get(key) || 0) + 1);
      return null;
    }
    // 4. A count tries every stored point as the opposite corner
    let total = 0;
    for (const [key, count] of points) {
      const [a, b] = key.split(",").map(Number);
      // 5. Skip a point that is not diagonal to the query point
      if (a === x || Math.abs(a - x) !== Math.abs(b - y)) continue;
      // 6. The other two corners are fixed: multiply the three counts
      total +=
        count * (points.get(x + "," + b) || 0) * (points.get(a + "," + y) || 0);
    }
    return total;
  });
}

def solve(operations, values):
    # 1. Keep a count for every point that has been added
    points = {}
    # 2. Handle the operations in order and give one result for each
    out = []
    for op, args in zip(operations, values):
        result = None
        if op == "add":
            # 3. An add raises the count of its point by one
            x, y = args
            points[(x, y)] = points.get((x, y), 0) + 1
        elif op == "count":
            # 4. A count tries every stored point as the opposite corner
            x, y = args
            result = 0
            for (px, py), count in points.items():
                # 5. Skip a point that is not diagonal to the query point
                if px == x or abs(px - x) != abs(py - y):
                    continue
                # 6. The other two corners are fixed: multiply the three counts
                result += count * points.get((x, py), 0) * points.get((px, y), 0)
        # "DetectSquares" and "add" leave the result as None.
        out.append(result)
    return out

Example 1, traced

Input
operations = ["DetectSquares","add","add","add","count","count","add","count"]
values = [[],[3,10],[11,2],[3,2],[11,10],[14,8],[11,2],[11,10]]

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

Why it works

Every square that has the query point as a corner has exactly one opposite corner, and that corner decides the other two. The loop meets each different stored point once and keeps only true opposite corners. For each one, every combination of one copy of each of the three corners is one way, so multiplying the three counts adds exactly the ways for that square.

Time and space

Time O(unique points) count; O(1) average add, extra space O(unique points). An add is one map update, about one step on average: that is the O(1) average add. A count goes through every different stored point once, with two lookups for each: O(unique points). The map holds one entry per different point: O(unique points) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Store the number of copies of each point, not only whether it is there. With a yes or no per point, the last count of example 1 gives 1 instead of 2: the second copy of (11, 2) is lost.
• A diagonal point does not mean the other two corners are stored. Count a missing corner as 0. After add (1, 1), count (0, 0) must give 0; without that 0, JavaScript gives NaN and a Python dict raises KeyError.
• Without the same-column check, add (0, 0) then count (0, 0) gives 1: a square of side 0. Without absolute values, add (0, 0), (1, 0), (1, 1) then count (0, 1) gives 0: the square's down-right corner is missed.

Pattern

Purpose-built data structure. Builds on Valid Anagram and Min Stack.

Keep going