2013. Detect Squares - Explanation

Problem Link

Description

You are given a stream of points consisting of x-y coordinates on a 2-D plane. Points can be added and queried as follows:

  • Add - new points can be added to the stream into a data structure. Duplicate points are allowed and should be treated as separate points.
  • Query - Given a single query point, count the number of ways to choose three additional points from the data structure such that the three points and the query point form a square. The square must have all sides parallel to the x-axis and y-axis, i.e. no diagonal squares are allowed. Recall that a square must have four equal sides.

Implement the CountSquares class:

  • CountSquares() Initializes the object.
  • void add(int[] point) Adds a new point point = [x, y].
  • int count(int[] point) Counts the number of ways to form valid squares with point point = [x, y] as described above.

Example 1:

Input: 
["CountSquares", "add", [[1, 1]], "add", [[2, 2]], "add", [[1, 2]], "count", [[2, 1]], "count", [[3, 3]], "add", [[2, 2]], "count", [[2, 1]]]
       
Output:
[null, null, null, null, 1, 0, null, 2]

Explanation:
CountSquares countSquares = new CountSquares();
countSquares.add([1, 1]);
countSquares.add([2, 2]);
countSquares.add([1, 2]);

countSquares.count([2, 1]);   // return 1.
countSquares.count([3, 3]);   // return 0.
countSquares.add([2, 2]);     // Duplicate points are allowed.
countSquares.count([2, 1]);   // return 2.

Constraints:

  • point.length == 2
  • 0 <= x, y <= 1000


Recommended Time & Space Complexity

You should aim for a solution with O(1) time for each add() call, O(n) time for each count() call, and O(n) space, where n is the total number of points.


Hint 1

Initially, we can store the points in a global list for the add() call. For the count() call, a brute force approach would use three nested loops to check other points except for the query point, resulting in an O(n^3) time solution. Can you think of a better way? Maybe you should consider the observation that can be drawn from the diagonal of a square.


Hint 2

In a square's diagonal, the absolute difference between the x-coordinates is equal to the absolute difference between the y-coordinates of the two endpoints, and neither difference can be zero. Using these two points, we can determine the other diagonal endpoints.


Hint 3

We store points in a hash map instead of a list for O(1) lookups, treating duplicate points as one while tracking their frequencies. For the count() function, we iterate through points that, along with the query point, can form a diagonal. Let the query point be (qx, qy) and the other point be (x, y), ensuring they form a diagonal. What could be the other two points? Maybe you should consider the points forming a right-to-left diagonal, treating (qx, qy) as the top-right corner.


Hint 4

The other two points are point1 (x, qy) and point2 (qx, y). For counting, we simply add count of point1 * count of point2 to the result res.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Hash Map - I

class CountSquares:
    def __init__(self):
        self.ptsCount = defaultdict(int)
        self.pts = []

    def add(self, point: List[int]) -> None:
        self.ptsCount[tuple(point)] += 1
        self.pts.append(point)

    def count(self, point: List[int]) -> int:
        res = 0
        px, py = point
        for x, y in self.pts:
            if (abs(py - y) != abs(px - x)) or x == px or y == py:
                continue
            res += self.ptsCount[(x, py)] * self.ptsCount[(px, y)]
        return res

Time & Space Complexity

  • Time complexity: O(1)O(1) for add()add(), O(n)O(n) for count()count().
  • Space complexity: O(n)O(n)

2. Hash Map - II

class CountSquares:

    def __init__(self):
        self.ptsCount = defaultdict(lambda: defaultdict(int))

    def add(self, point: List[int]) -> None:
        self.ptsCount[point[0]][point[1]] += 1

    def count(self, point: List[int]) -> int:
        res = 0
        x1, y1 = point
        for y2 in self.ptsCount[x1]:
            side = y2 - y1
            if side == 0:
                continue

            x3, x4 = x1 + side, x1 - side
            res += (self.ptsCount[x1][y2] * self.ptsCount[x3][y1] *
                    self.ptsCount[x3][y2])

            res += (self.ptsCount[x1][y2] * self.ptsCount[x4][y1] *
                    self.ptsCount[x4][y2])
        return res

Time & Space Complexity

  • Time complexity: O(1)O(1) for add()add(), O(n)O(n) for count()count().
  • Space complexity: O(n)O(n)