Detect Squares

Medium

The problem

Build a structure that stores points on a plane. Add(point) stores a point [x, y]; the same point can be added several times and each copy counts. Count(point) returns how many ways there are to pick three stored points that, together with the query point, make the corners of a square with sides parallel to the x and y axes and an area bigger than 0.

Example 1
Input: Constructor(); Add([3, 10]); Add([11, 2]); Add([3, 2]); Count([11, 10]); Count([14, 8]); Add([11, 2]); Count([11, 10])
Output: Count([11, 10]) = 1, then Count([14, 8]) = 0, then the last Count([11, 10]) = 2
The first query closes the square with (3,10), (11,2) and (3,2). No stored points can make a square with (14,8). After adding a second copy of (11,2) there are two ways to pick that corner.

Limits

0 ≤ x, y ≤ 1,000
At most 3,000 calls in total to Add and Count
Squares must have sides parallel to the axes and a positive area

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

For a query point, treat each stored point on the same row or diagonal as a possible opposite corner.

The idea

Count points in a map. For a query (x,y) iterate over distinct points that form a diagonal (|dx|==|dy|≠0) and multiply the counts of the two missing corners.

Target: add O(1), count O(n)

Go function shape

type DetectSquares struct{}
func Constructor() DetectSquares
func (d *DetectSquares) Add(point []int)
func (d *DetectSquares) Count(point []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// DetectSquares stores how many times each point was added. For a query point, every stored point on a diagonal
// (same distance in x and y, not zero) is a possible opposite corner; the other two corners must also exist,
// and the number of squares is the product of the three counts.
type DetectSquares struct{ count map[[2]int]int }

func NewDetectSquares() *DetectSquares { return &DetectSquares{count: map[[2]int]int{}} }

func (d *DetectSquares) Add(point []int) { d.count[[2]int{point[0], point[1]}]++ }

func (d *DetectSquares) Count(point []int) int {
	qx, qy := point[0], point[1]
	total := 0
	for p, n := range d.count {
		dx, dy := p[0]-qx, p[1]-qy
		if dx == 0 || abs(dx) != abs(dy) {
			continue // not a diagonal corner
		}
		total += n * d.count[[2]int{qx, p[1]}] * d.count[[2]int{p[0], qy}]
	}
	return total
}

Read the lesson: Bit Manipulation & Math