Skip to content

173 — Detect Squares

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

173 — Detect Squares

LeetCode 2013 · Medium. Design a data structure that supports adding points on a 2-D plane (the same point may be added more than once, and each occurrence counts separately) and, given a query point, counting the number of ways to choose two other added points that form an axis-aligned square with the query point (all four corners at right angles, sides parallel to the axes).

🍽️ Intuition

Picture a corkboard where you're pinning up points one at a time, and every so often someone points at a spot and asks: "how many axis-aligned squares can you build using this spot as one corner and three pins already on the board?" Since the square must be axis-aligned, once you fix the query corner and pick any other pinned point that shares the query's x-coordinate (a point directly above or below it — a candidate for the opposite corner on the same vertical side), the entire square is already determined: its side length is just the vertical distance between those two points, and the two remaining corners are locked in at a fixed horizontal offset from each of them. All that's left to check is: are those two remaining corners actually pinned on the board?

query point Q = (11, 10)

pinned points:  (3, 10)   (3, 2)             (11, 2)

Q shares x=11 with (11, 2): side length = |10 - 2| = 8
remaining corners needed: (11 - 8, 10) = (3, 10)  <- pinned!
                           (11 - 8, 2)  = (3, 2)   <- pinned!
=> one full square found: (11,10) - (11,2) - (3,2) - (3,10)

🚩 Pattern-Recognition Cue

"Count squares formable with a query point and previously added points" is a coordinate-lookup signal: since the square is axis-aligned, fixing the query point and one same-column (or same-row) partner point completely determines where the other two corners must be — turning "search for a square" into "check whether two specific coordinates were ever added," which is exactly what a hash map keyed by coordinate answers in O(1).

🐢 Brute Force

Store every added point in a plain list (duplicates included). For a query, scan the list for points sharing the query's x-coordinate as a candidate vertical partner, then scan the list again (twice) to count how many stored points sit at each of the two possible "other corner" locations.

class DetectSquaresBruteForce {
    private var points: [(Int, Int)] = []

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

    func count(_ point: [Int]) -> Int {
        let (px, py) = (point[0], point[1])
        var total = 0

        for (x2, y2) in points where x2 == px && y2 != py {
            let side = abs(y2 - py)

            for xOther in [px + side, px - side] {
                let cornerACount = points.filter { $0 == (xOther, py) }.count
                let cornerBCount = points.filter { $0 == (xOther, y2) }.count
                total += cornerACount * cornerBCount
            }
        }

        return total
    }
}

// smoke test
let bruteDetector = DetectSquaresBruteForce()
bruteDetector.add([3, 10])
bruteDetector.add([11, 2])
bruteDetector.add([3, 2])
print(bruteDetector.count([11, 10]))   // 1
bruteDetector.add([11, 2])
print(bruteDetector.count([11, 10]))   // 2
print(bruteDetector.count([14, 8]))    // 0

Big-O: add is O(1). count is O(n²) in the worst case — the outer scan over same-column points is O(n), and each of the two inner filter calls re-scans the entire list. O(n) space for the stored points.

🚀 Optimal

Store point counts in a hash map keyed by x, then by y (pointCount[x][y] = how many times (x, y) was added). For a query, only iterate over the distinct y-values already recorded at the query's x-coordinate, and look up the two remaining corners directly instead of rescanning anything.

class DetectSquares {
    private var pointCount: [Int: [Int: Int]] = [:]   // x -> (y -> count of points added at (x, y))

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

    func count(_ point: [Int]) -> Int {
        let (px, py) = (point[0], point[1])
        guard let sameColumn = pointCount[px] else { return 0 }

        var total = 0
        for (y2, countAtY2) in sameColumn where y2 != py {
            let side = abs(y2 - py)

            for xOther in [px + side, px - side] {
                let cornerACount = pointCount[xOther]?[py] ?? 0
                let cornerBCount = pointCount[xOther]?[y2] ?? 0
                total += countAtY2 * cornerACount * cornerBCount
            }
        }

        return total
    }
}

// smoke test — same sequence as the brute force
let detector = DetectSquares()
detector.add([3, 10])
detector.add([11, 2])
detector.add([3, 2])
print(detector.count([11, 10]))   // 1
detector.add([11, 2])
print(detector.count([11, 10]))   // 2
print(detector.count([14, 8]))    // 0

Big-O: add is O(1). count is O(k) where k is the number of distinct points sharing the query's x-coordinate (worst case O(n)), since each candidate now costs two O(1) hash lookups instead of two full-list scans. O(n) space for the hash map.

🔑 The Key Insight

The brute force's two filter calls inside the inner loop are answering the exact same question every time: "how many times was this specific coordinate added?" That question doesn't need a fresh O(n) scan of every stored point each time it's asked — it only needs a lookup table that's kept up to date as points are added. Once pointCount exists, the outer loop only has to consider points that are actually candidates (those sharing the query's x-coordinate), and the two remaining corners are confirmed with two O(1) dictionary reads instead of two more full passes over every point ever added.

🔗 Related Chapters

  • Hash Maps and Hash Sets — the coordinate-keyed count map that turns "was this point added, and how many times?" into an O(1) lookup instead of a scan.
  • Matrix Traversal — disclosed as a loose fit, not a strong one: there's no actual grid traversal here — no neighbors are visited and nothing is walked step by step. The only echo is that the nested x -> y -> count map treats the plane as a sparse 2-D grid of coordinates, the same row/column framing this chapter uses for dense grids, just without any adjacency or movement between cells.

🧸 Memory Sentence

Detect Squares is a corkboard of pinned points — fix the query corner and one same-column pin, and the other two corners are already determined; just check whether they're pinned too.

✅ Check Your Understanding

  1. Why does the query only need to check points sharing the query's x-coordinate as candidate partners — why not also separately check points sharing the query's y-coordinate?
  2. In the optimal solution, total += countAtY2 * cornerACount * cornerBCount multiplies three counts together rather than just adding 1 per match. Why is this multiplication necessary to correctly count squares when the same point has been added more than once?
  3. Walk through why count([11, 10]) returns 1 before the second [11, 2] is added, but 2 afterward — which specific multiplication in the formula changes?
  4. Why does count skip any stored point where y2 == py (same y as the query), even though that point does share the query's x-coordinate?

⬅️ Previous: Multiply Strings · Next: Single Number ➡️

Clone this wiki locally