A drawing app lets users drop pins on a grid, and it wants to suggest squares. Build a class PointBoard:
PointBoard()starts with no points.add(x, y)places a point at(x, y). The same position can be added several times; each copy is a separate point.count(x, y) -> intreturns how many ways you can pick three stored points that, together with the query point(x, y), form the four corners of a square with sides parallel to the axes and positive area. Using a different copy of a repeated point counts as a different way. The query point itself is not stored.
board = PointBoard()
board.add(2, 2)
board.add(2, 6)
board.add(6, 2)
board.count(6, 6) # 1 (corners (2,2), (2,6), (6,2) and the query (6,6))
board.count(2, 4) # 0
board.add(6, 2) # a second copy of (6, 2)
board.count(6, 6) # 2 (either copy of (6, 2) can be used)
board.add(10, 2)
board.add(10, 6)
board.count(6, 6) # 4 (the left square in 2 ways, and the square with (10,2), (10,6), (6,2) in 2 ways)
Constraints:
0 <= x, y <= 10^4.- At most
10^5calls in total. Answers can exceed2^31.
Trying every combination of stored points, or even looping over every stored point on each count, is too slow. Aim for add in O(1) and count in time proportional to the number of distinct stored positions that share the query's x coordinate.
Show hint
Keep a tally of how many copies sit at each position, and also group positions by their x. Any square through (x, y) has a corner directly above or below it; that corner fixes the side length, and the other two corners are then determined.