Detect Squares

MEDIUM✓ CHIP-TIMEDLC #2013 — FULL STATEMENT ↗

The drill: A structure that remembers every point fed into it, then reports how many axis-aligned squares could be formed using a queried point as one corner and any three previously stored points as the rest — duplicate points at the same coordinate each count separately.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A running structure gets built up by feeding it points, one at a time, each with an x and a y coordinate — the same coordinate pair can be added more than once, and each addition is remembered separately, not merged.

Separately, the structure can be asked to count axis-aligned squares: for a query point, how many squares exist whose sides run parallel to the axes, using the query point as one corner and any three previously added points as the other three corners.

A duplicate point counts as its own distinct choice for a corner, so if the same coordinate was added twice, a square using it as a corner is counted once for each of those additions — this site verifies the drill by mixing add and count calls in sequence and checking every count against the expected value.

EX 01

DetectSquares()

add([3, 10])

add([11, 2])

add([3, 2])

count([11, 10]) → 1

count([14, 8]) → 0

add([11, 2])

count([11, 10]) → 2

DUPLICATE POINTS MULTIPLY THE COUNT

EX 02

DetectSquares()

count([0, 0]) → 0

NOTHING ADDED YET

EX 03

DetectSquares()

add([5, 5])

count([5, 5]) → 0

ONE STORED POINT CAN'T COMPLETE A SQUARE BY ITSELF

up to a few thousand total add and count calls across a run
coordinates are non-negative integers within a modest range
the same point can be added multiple times and each counts separately
squares counted are always axis-aligned, sides parallel to the x and y axes

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A square through the query point needs exactly one other stored point sharing a coordinate with it — same x or same y. Start the search there instead of comparing every pair of stored points.

HINT 2 THE STRUCTURE

Once you've picked a partner that shares, say, the x-coordinate, the side length is forced: it's the vertical gap between the two y-values. The other two corners of the square sit exactly that many units to the left and to the right of both points.

HINT 3 ONE STEP FROM THE ANSWER

For every stored point (x, y2) sharing x with the query (x, y), let d = y2 − y. Multiply the counts of (x, y2), (x+d, y), (x+d, y2) — then repeat for (x−d, y) and (x−d, y2) — and sum every combination, since a duplicate point multiplies the ways.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE COLUMN LOOKUPPATTERN · COLUMN FREQUENCY MAPadd(0,0) · add(0,2) · add(2,0) · count(2,2) · add(0,0) · count(2,2)

new

add (0,0)

add (0,2)

add (2,0)

count (2,2)

add (0,0)

count (2,2)

THE COLUMN MAP — X → {Y: COUNT}

— empty —

STEP 1

DetectSquares indexes points by column x, then by row y. add just stores; count asks how many axis-aligned squares close through the query.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/detect-squares.py — RACE PACE

LANG ▸

PACE ▸

class DetectSquares:
    def __init__(self):
        self.cols = collections.defaultdict(collections.Counter)  # x -> {y: count}

    def add(self, point: List[int]) -> None:
        x, y = point
        self.cols[x][y] += 1

    def count(self, point: List[int]) -> int:
        x, y = point
        if x not in self.cols:
            return 0
        total = 0
        for y2, c in self.cols[x].items():
            if y2 == y:
                continue
            d = y2 - y
            for x2 in (x + d, x - d):
                if x2 in self.cols:
                    total += c * self.cols[x2][y] * self.cols[x2][y2]
        return total

TIME O(1) ADD · O(N) COUNTSPACE O(N)PYTHON · RACE PACE · 21 LN

class DetectSquares:
    def __init__(self):
        self.points = []  # flat list of (x, y), duplicates allowed

    def add(self, point: List[int]) -> None:
        self.points.append((point[0], point[1]))

    def _occurrences(self, x: int, y: int) -> int:
        return sum(1 for px, py in self.points if px == x and py == y)

    def count(self, point: List[int]) -> int:
        x, y = point
        total = 0
        for px, py in self.points:          # re-scan everything for a same-column partner
            if px == x and py != y:
                d = py - y
                total += self._occurrences(x + d, y) * self._occurrences(x + d, py)
                total += self._occurrences(x - d, y) * self._occurrences(x - d, py)
        return total

TIME O(1) ADD · O(N²) COUNTSPACE O(N)PYTHON · TRAINING PACE · 19 LN

class DetectSquares {
    private final Map<Integer, Map<Integer, Integer>> cols = new HashMap<>();

    public DetectSquares() {
    }

    public void add(int[] point) {
        int x = point[0], y = point[1];
        cols.computeIfAbsent(x, k -> new HashMap<>()).merge(y, 1, Integer::sum);
    }

    public int count(int[] point) {
        int x = point[0], y = point[1];
        Map<Integer, Integer> column = cols.get(x);
        if (column == null) {
            return 0;
        }
        int total = 0;
        for (Map.Entry<Integer, Integer> entry : column.entrySet()) {
            int y2 = entry.getKey(), c = entry.getValue();
            if (y2 == y) {
                continue;
            }
            int d = y2 - y;
            for (int x2 : new int[] { x + d, x - d }) {
                Map<Integer, Integer> other = cols.get(x2);
                if (other != null) {
                    total += c * other.getOrDefault(y, 0) * other.getOrDefault(y2, 0);
                }
            }
        }
        return total;
    }
}

TIME O(1) ADD · O(N) COUNTSPACE O(N)JAVA · RACE PACE · 34 LN

class DetectSquares {
    private final List<int[]> points = new ArrayList<>(); // flat list, duplicates allowed

    public DetectSquares() {
    }

    public void add(int[] point) {
        points.add(new int[] { point[0], point[1] });
    }

    private int occurrences(int x, int y) {
        int count = 0;
        for (int[] p : points) {
            if (p[0] == x && p[1] == y) {
                count++;
            }
        }
        return count;
    }

    public int count(int[] point) {
        int x = point[0], y = point[1];
        int total = 0;
        for (int[] p : points) {                 // re-scan everything for a same-column partner
            if (p[0] == x && p[1] != y) {
                int d = p[1] - y;
                total += occurrences(x + d, y) * occurrences(x + d, p[1]);
                total += occurrences(x - d, y) * occurrences(x - d, p[1]);
            }
        }
        return total;
    }
}

TIME O(1) ADD · O(N²) COUNTSPACE O(N)JAVA · TRAINING PACE · 33 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED