Coordinate geometry with hashing

35 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You are given five points on a grid: (1,1), (1,3), (3,1), (3,3) and (4,1), and asked for the smallest rectangle, with sides parallel to the axes, whose four corners are all among the points. By hand you would try to spot four points that line up: (1,1), (1,3), (3,1), (3,3) do, with area 2 × 2 = 4. For five points your eye finds it. For 500 points you cannot, and the obvious program that tries every group of four points does 500 · 499 · 498 · 497 / 24, about 2.6 billion, checks.

Build the structure, one piece at a time

The first piece is a hash set of the points, so that "is (3,3) one of the given points?" costs one lookup instead of a scan. Put all five points in.

The second piece is an observation that cuts the work: a rectangle with axis-parallel sides is fixed by one diagonal. If (x₁, y₁) and (x₂, y₂) are opposite corners, the other two corners must be (x₁, y₂) and (x₂, y₁). So instead of choosing four points, choose two and ask the set whether the other two exist. Running through the pairs:

1. (1,1) and (3,3): different x and different y, so a real diagonal. Corners (1,3) and (3,1): both in the set. Area |3 − 1| · |3 − 1| = 4. Best so far 4.
2. (1,1) and (1,3): same x, so this is a side, not a diagonal. Skip.
3. (1,3) and (4,1): corners (1,1) and (4,3). (4,3) is missing. Skip.
4. (3,1) and (4,1): same y. Skip.
5. Every other pair is a side or has a missing corner. Answer 4.

Other point problems use the same two ideas with a different key. Max Points on a Line hashes the direction between pairs; the direction (dx, dy) is divided by its gcd and given a fixed sign so that (2,4), (1,2) and (−1,−2) all become the same key (1,2). Number of Boomerangs hashes squared distances from each centre. K Closest Points needs no hashing at all, just squared distances and a heap or sort.

Why it is correct

Every axis-parallel rectangle among the points has two diagonals, and each diagonal is a pair of points with different x and different y. The loop visits every pair, so it visits both diagonals of every rectangle, and for each it checks exactly the two points that would complete it. A rectangle is counted when its corners exist and skipped otherwise, so the minimum found is the true minimum. Keeping the smaller area as you go is safe because the area of a candidate does not depend on the order of discovery.

For the direction key, the invariant is that two pairs get the same key exactly when they point along the same line through the centre point. Dividing by the gcd removes scale, and fixing the sign removes orientation, so (1,2) and (−1,−2) collapse together, which is what "same line" means.

Why it is fast

There are n(n − 1)/2 pairs. For each pair the set answers two membership questions in expected O(1), so the whole run is O(n²). For 500 points that is about 125,000 pair checks, against 2.6 billion for choosing four points. Direction hashing is the same shape: for each centre, O(n) keys into a map, O(n²) overall.

pairs = n(n − 1)/2, quadruples = n(n − 1)(n − 2)(n − 3)/24

How to recognise it in an interview

Cues: a list of points on a plane, "rectangle", "square", "collinear", "on the same line", "equidistant", "closest to the origin". Say: "I will put the points in a hash set and iterate over pairs, deriving the remaining geometry from each pair, so the cost is quadratic rather than quartic".

Minimum Area Rectangle is the walk-through above. Minimum Area Rectangle II drops the axis-parallel condition; there the diagonal is identified by its midpoint and length, two diagonals with the same key form a rectangle, and the key is what goes into the map. Count Number of Trapezoids I groups segments by slope key and counts pairs within each group.

02The idea in one line

Hash points or slopes; count rectangles/lines by pairs.

Reach for it when: Minimum area rectangle, max points on a line, k closest, valid square, boomerangs.

Cost: O(n²) time.

03The walk-through, step by step

The video works one example: Minimum Area Rectangle on 5 points. These are its captions in order, so you can follow without the video or check a step you missed.

1. Put every point in a hash set of (x, y)
2. Diagonal (1,1)–(3,3): corners (1,3),(3,1) exist, area 4
3. Diagonal (1,1)–(2,2): a corner is missing, skip
4. Diagonal (2,2)–(3,3): a corner is missing, skip
5. Diagonal (1,3)–(4,1): a corner is missing, skip
6. (3,1) and (4,1) share a row or column: not a diagonal
7. (1,1) and (4,1) share a row or column: not a diagonal
8. Every pair of points was tried as a diagonal: best = 4
9. Pairs × O(1) set lookups: O(n²) time

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Math: Fast exponentiation, GCD and number theory, Digit-by-digit arithmetic, Random pick and reservoir sampling.