loading

Detect Squares — Step-by-Step Visualization

mediumLeetCode #2013ArrayHash TableDesignCounting

You are given a stream of points on a 2D plane. Each point has integer coordinates. Implement the `DetectSquares` class: (1) `add(point)`: Adds a new point [x, y] to the data structure. Duplicate points are allowed. (2) `count(point)`: Counts the number of ways to form axis-aligned squares with the given [x, y] as one of the four corners, where the other three corners are points already added.

Algorithm Pattern

Axis-Aligned Square Geometry

Key Idea

A square is defined by two diagonally opposite corners. If we are given a point `(x, y)` as one corner, then any other point `(x1, y1)` in the database can potentially be the diagonally opposite corner. For this to form a square: (1) `|x - x1| == |y - y1|` and (2) `|x - x1| > 0`. If these hold, the other two corners must be `(x, y1)` and `(x1, y)`. The number of ways to form this square is `count[(x1, y1)] * count[(x, y1)] * count[(x1, y)]`.

Step-by-Step Approach

  1. Maintain a frequency map of all added points: `(x, y) -> frequency`.
  2. To `add(point)`, increment `map[point]`.
  3. To `count(point)`, iterate through all unique points `(x1, y1)` in the map.
  4. If `(x1, y1)` is a valid diagonal corner, look up the frequencies of the other two corners.
  5. Multiply the three frequencies and add to the total count.

Common Gotchas

  • Duplicate points matter! The problem asks for the number of *ways* to form squares.
  • Axis-aligned means the sides are parallel to the x and y axes.

Related Problems

← All problems