#2013

Detect Squares

medium· Math & Geometryruns: 0

Design an algorithm that supports adding new points to a stream and counting the number of axis-aligned squares with a query point as one of the corners. Implement DetectSquares with add(point) that adds a point and count(point) that returns the number of axis-aligned squares with the given point as one corner. Points may be repeated.

wpm 0acc 100%time 0:000 / 569

from collections import defaultdict

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

    def add(self, point: list[int]) -> None:
        self.counts[tuple(point)] += 1
        self.points.append(tuple(point))

    def count(self, point: list[int]) -> int:
        px, py = point
        total = 0
        for x, y in self.points:
            if abs(x - px) != abs(y - py) or x == px or y == py:
                continue
            total += self.counts[(x, py)] * self.counts[(px, y)]
        return total

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.