Detect Squares

The key idea

Problem

You are given a stream of points on the X-Y plane. Design an algorithm that:

- Adds new points from the stream into a data structure. Duplicate points are allowed and should be treated as different points.
- Counts the number of ways to choose three points from the data structure such that the three chosen points and a given query point form an axis-aligned square with positive area.

An axis-aligned square is a square whose edges are all the same length and are parallel to the X-axis and Y-axis.

Implement the DetectSquares class:

- DetectSquares() initializes the object.
- add(point) adds a new point point = [x, y] to the data structure.
- count(point) counts the number of ways to form axis-aligned squares with the query point point = [x, y] as described above, and returns that count.

Constraints

• point.length == 2
• 0 <= x, y <= 1000
• At most 3000 calls in total will be made to add and count

Examples

Complexity

Time: O(n) per count, O(1) per add Space: O(n)

More Design problems

• Binary Search Tree IteratorMEDIUM
• Design Circular QueueMEDIUM
• Design HashMapEASY
• Design HashSetEASY
• Design TwitterMEDIUM
• Encode and Decode StringsMEDIUM
• Implement Queue using StacksEASY
• Implement Stack using QueuesEASY
• Insert Delete GetRandom O(1)MEDIUM
• LFU CacheHARD
• LRU CacheMEDIUM
• Maximum Frequency StackHARD