2013. Detect Squares (Medium)

Problem

Design a data structure with:

• add(point), add a 2D point (with possible duplicates).
• count(point), count the number of axis-aligned squares whose corners include three stored points and the given query point.

Example

d = DetectSquares()
d.add([3,10]); d.add([11,2]); d.add([3,2])
d.count([11,10])  // 1
d.count([14,8])   // 0
d.add([11,2])
d.count([11,10])  // 2

LeetCode 2013 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, pairwise check

On count(p), scan every ordered pair of stored points; test if one is q’s column-mate and the other is q’s row-mate, with equal side lengths. The diagonal corner is (bx, ay); add its multiplicity.

Python

from collections import defaultdict

class DetectSquares:
    def __init__(self):
        self.counts = defaultdict(int)
        self.points_list = []                     # stored with duplicates

    def add(self, point):
        p = tuple(point)
        self.counts[p] += 1
        self.points_list.append(p)

    def count(self, point):
        qx, qy = point
        total = 0
        for ax, ay in self.points_list:           # A: column-mate of q (ax == qx)
            for bx, by in self.points_list:       # B: row-mate of q (by == qy)
                if ax != qx or by != qy:
                    continue
                if ay == qy or bx == qx:          # collapsed square
                    continue
                if abs(ay - qy) != abs(bx - qx):  # not equal sides
                    continue
                total += self.counts[(bx, ay)]    # diagonal multiplicity
        return total

Swift

final class DetectSquares {
    private var points: [(x: Int, y: Int)] = []

    init() {}

    func add(_ point: [Int]) { points.append((point[0], point[1])) }

    func count(_ point: [Int]) -> Int {
        let qx = point[0], qy = point[1]
        var total = 0
        for horizontal in points where horizontal.y == qy && horizontal.x != qx {
            for vertical in points where vertical.x == qx && vertical.y != qy {
                guard abs(horizontal.x - qx) == abs(vertical.y - qy) else { continue }
                total += points.reduce(0) { count, candidate in
                    count + (candidate.x == horizontal.x && candidate.y == vertical.y ? 1 : 0)
                }
            }
        }
        return total
    }
}

Iterating points_list with duplicates means the multiplicities of A and B are baked in implicitly; only D’s multiplicity is read from counts. Each square formed by (q, A, B, D) is counted exactly once.

Complexity

• count: $O(n²)$.
• Space: $O(n)$.

Approach 2: Count map + diagonal fix (canonical)

Fix the query point (qx, qy). For each stored point (x, y):

• If |x - qx| == |y - qy| and neither is 0, (x, y) is a diagonal corner of a square with (qx, qy).
• The other two corners are (x, qy) and (qx, y).
• Count the squares: counts[(x, y)] * counts[(x, qy)] * counts[(qx, y)].

Use a Counter of points.

Python

from collections import defaultdict

class DetectSquares:
    def __init__(self):
        self.counts = defaultdict(int)          # L1: O(1)
        self.points = set()                     # L2: O(1), distinct points for iteration

    def add(self, point):
        p = (point[0], point[1])
        self.counts[p] += 1                     # L3: O(1) amortized
        self.points.add(p)                      # L4: O(1) amortized

    def count(self, point):
        qx, qy = point
        total = 0
        for x, y in list(self.points):          # L5: iterate all distinct points, O(n)
            if abs(x - qx) == abs(y - qy) and x != qx and y != qy:  # L6: O(1)
                total += (self.counts[(x, y)]
                          * self.counts[(x, qy)]
                          * self.counts[(qx, y)])  # L7: O(1)
        return total

TypeScript

class DetectSquares {
    private counts: Map<string, number> = new Map();   // L1: O(1)
    private points: Set<string> = new Set();            // L2: O(1), distinct points for iteration

    private key(x: number, y: number): string {
        return `${x},${y}`;
    }

    add(point: number[]): void {
        const k = this.key(point[0], point[1]);
        this.counts.set(k, (this.counts.get(k) ?? 0) + 1);  // L3: O(1) amortized
        this.points.add(k);                                   // L4: O(1) amortized
    }

    count(point: number[]): number {
        const [qx, qy] = point;
        let total = 0;
        for (const pk of this.points) {                       // L5: iterate all distinct points, O(n)
            const [x, y] = pk.split(',').map(Number);
            if (Math.abs(x - qx) === Math.abs(y - qy) && x !== qx && y !== qy) {  // L6: O(1)
                total += (this.counts.get(pk) ?? 0)
                       * (this.counts.get(this.key(x, qy)) ?? 0)
                       * (this.counts.get(this.key(qx, y)) ?? 0);  // L7: O(1)
            }
        }
        return total;
    }
}

Go

type DetectSquares struct {
    counts map[[2]int]int  // L1: O(1)
    points [][2]int        // L2: O(1), distinct points for iteration
    seen   map[[2]int]bool
}

func Constructor() DetectSquares {
    return DetectSquares{counts: make(map[[2]int]int), seen: make(map[[2]int]bool)}
}

func (ds *DetectSquares) Add(point []int) {
    p := [2]int{point[0], point[1]}
    ds.counts[p]++                              // L3: O(1) amortized
    if !ds.seen[p] { ds.seen[p] = true; ds.points = append(ds.points, p) }  // L4: O(1) amortized
}

func (ds *DetectSquares) Count(point []int) int {
    qx, qy := point[0], point[1]
    total := 0
    for _, p := range ds.points {              // L5: iterate all distinct points, O(n)
        x, y := p[0], p[1]
        dx, dy := x-qx, y-qy
        if dx < 0 { dx = -dx }
        if dy < 0 { dy = -dy }
        if dx == dy && x != qx && y != qy {    // L6: O(1)
            total += ds.counts[[2]int{x, y}] *
                ds.counts[[2]int{x, qy}] *
                ds.counts[[2]int{qx, y}]       // L7: O(1)
        }
    }
    return total
}

Swift

private struct Point: Hashable {
    let x: Int
    let y: Int
}

final class DetectSquares {
    private var counts: [Point: Int] = [:]

    init() {}

    func add(_ point: [Int]) {
        counts[Point(x: point[0], y: point[1]), default: 0] += 1
    }

    func count(_ point: [Int]) -> Int {
        let query = Point(x: point[0], y: point[1])
        var total = 0
        for (diagonal, frequency) in counts {
            let dx = diagonal.x - query.x
            let dy = diagonal.y - query.y
            guard dx != 0, abs(dx) == abs(dy) else { continue }
            total += frequency
                * counts[Point(x: diagonal.x, y: query.y), default: 0]
                * counts[Point(x: query.x, y: diagonal.y), default: 0]
        }
        return total
    }
}

Where the time goes, line by line

Variables: n = number of distinct stored points.

Line	Per-call cost	Times executed	Contribution
L3, L4 (add)	$O(1)$ amortized	1 per call	$O(1)$ per add
L5-L7 (count scan)	$O(1)$	n	$O(n)$ ← dominates

add is $O(1)$; count scans all distinct stored points.

Complexity

• add: $O(1)$ amortized.
• count: $O(n)$.
• Space: $O(n)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Hash-map keyed by x-coordinate

Maintain by_x[x] = set of y's seen at that x. On count(qx, qy), iterate y’s at qx, compute side length = |y - qy|, check the two other corners.

Python

from collections import defaultdict

class DetectSquares:
    def __init__(self):
        self.counts = defaultdict(int)
        self.by_x = defaultdict(set)

    def add(self, point):
        self.counts[tuple(point)] += 1          # L1: O(1)
        self.by_x[point[0]].add(point[1])       # L2: O(1)

    def count(self, point):
        qx, qy = point
        total = 0
        for y in self.by_x[qx]:                # L3: iterate y's at qx, O(k)
            if y == qy:
                continue
            side = abs(y - qy)                  # L4: O(1)
            for dx in (-side, side):            # L5: two candidate x offsets
                nx = qx + dx
                total += (self.counts.get((qx, y), 0)
                          * self.counts.get((nx, qy), 0)
                          * self.counts.get((nx, y), 0))  # L6: O(1)
        return total

Swift

final class DetectSquares {
    private var columns: [Int: [Int: Int]] = [:]

    init() {}

    func add(_ point: [Int]) {
        columns[point[0], default: [:]][point[1], default: 0] += 1
    }

    func count(_ point: [Int]) -> Int {
        let x = point[0], y = point[1]
        guard let verticalPoints = columns[x] else { return 0 }
        var total = 0
        for (otherY, verticalFrequency) in verticalPoints where otherY != y {
            let side = otherY - y
            for otherX in [x - side, x + side] {
                let otherColumn = columns[otherX] ?? [:]
                total += verticalFrequency
                    * otherColumn[y, default: 0]
                    * otherColumn[otherY, default: 0]
            }
        }
        return total
    }
}

Where the time goes, line by line

Variables: n = total stored points, k = number of distinct y-values at the queried x-coordinate.

Line	Per-call cost	Times executed	Contribution
L1, L2 (add)	$O(1)$ amortized	1 per call	$O(1)$ per add
L3-L6 (count scan)	$O(1)$	k	$O(k)$ ← dominates

count is $O(k)$ where k is distinct y-values at qx; worst case k = n if all points share the same x.

Complexity

• add: $O(1)$ amortized.
• count: $O(k)$ where k = number of distinct y’s at qx.
• Space: $O(n)$.

Slightly more efficient than Approach 2 when points cluster along few columns.

Summary

Approach	count time	Space
Pairwise scan	$O(n²)$	$O(n)$
Count map + diagonal fix	$O(n)$	$O(n)$
Keyed by x-coordinate	$O(k)$ per column	$O(n)$

The “fix a diagonal corner, multiply counts of the other three” pattern applies to many “count configurations” problems.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_2013.py and run.
# Uses the canonical implementation (Approach 2: count map + diagonal fix).

from collections import defaultdict

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

    def add(self, point):
        p = (point[0], point[1])
        self.counts[p] += 1
        self.points.add(p)

    def count(self, point):
        qx, qy = point
        total = 0
        for x, y in list(self.points):
            if abs(x - qx) == abs(y - qy) and x != qx and y != qy:
                total += (self.counts[(x, y)]
                          * self.counts[(x, qy)]
                          * self.counts[(qx, y)])
        return total

def _run_tests():
    d = DetectSquares()
    d.add([3, 10]); d.add([11, 2]); d.add([3, 2])
    assert d.count([11, 10]) == 1
    assert d.count([14, 8]) == 0
    d.add([11, 2])
    assert d.count([11, 10]) == 2   # duplicate point doubles the count

    d2 = DetectSquares()
    assert d2.count([0, 0]) == 0   # empty data structure

    d3 = DetectSquares()
    d3.add([0, 0]); d3.add([2, 0]); d3.add([0, 2]); d3.add([2, 2])
    assert d3.count([0, 0]) == 1   # query is itself a corner of the square

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class DetectSquares {
    private counts: Map<string, number> = new Map();
    private points: Set<string> = new Set();
    private key(x: number, y: number): string { return `${x},${y}`; }

    add(point: number[]): void {
        const k = this.key(point[0], point[1]);
        this.counts.set(k, (this.counts.get(k) ?? 0) + 1);
        this.points.add(k);
    }

    count(point: number[]): number {
        const [qx, qy] = point;
        let total = 0;
        for (const pk of this.points) {
            const [x, y] = pk.split(',').map(Number);
            if (Math.abs(x - qx) === Math.abs(y - qy) && x !== qx && y !== qy) {
                total += (this.counts.get(pk) ?? 0)
                       * (this.counts.get(this.key(x, qy)) ?? 0)
                       * (this.counts.get(this.key(qx, y)) ?? 0);
            }
        }
        return total;
    }
}

const d = new DetectSquares();
d.add([3, 10]); d.add([11, 2]); d.add([3, 2]);
console.assert(d.count([11, 10]) === 1);
console.assert(d.count([14, 8]) === 0);
d.add([11, 2]);
console.assert(d.count([11, 10]) === 2);
const d2 = new DetectSquares();
console.assert(d2.count([0, 0]) === 0);
const d3 = new DetectSquares();
d3.add([0, 0]); d3.add([2, 0]); d3.add([0, 2]); d3.add([2, 2]);
console.assert(d3.count([0, 0]) === 1);
console.log('all tests pass');

Related data structures

• Hash Tables, point-multiset counts; column index

Related concepts

• Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.
• Math and Number Theory, the arithmetic invariant behind digits, divisibility, modulo behavior, and identities.