Scale Engineer

Detect Squares

Med
#1833Time: `add(point)`: `O(1)` `count(point)`: `O(M * N)`, where `N` is the total number of points added and `M` is the number of unique points. In the worst case where all points are unique (`M=N`), the complexity is `O(N^2)`. This can be too slow if the number of `count` calls is high or `N` is large.Space: `O(N)` to store all the points in the list. The `count` method temporarily uses an additional `O(M)` space for the `HashSet` of unique points, where `N` is the total number of points and `M` is the number of unique points.
Patterns
DesignCounting
Data structures
ArrayHash Table

Prompt

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.
  • Given a query point, counts the number of ways to choose three points from the data structure such that the three points and the 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 either parallel or perpendicular to the x-axis and y-axis.

Implement the DetectSquares class:

  • DetectSquares() Initializes the object with an empty data structure.
  • void add(int[] point) Adds a new point point = [x, y] to the data structure.
  • int count(int[] point) Counts the number of ways to form axis-aligned squares with point point = [x, y] as described above.

 

Example 1:

Input
["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
Output
[null, null, null, null, 1, 0, null, 2]

Explanation
DetectSquares detectSquares = new DetectSquares();
detectSquares.add([3, 10]);
detectSquares.add([11, 2]);
detectSquares.add([3, 2]);
detectSquares.count([11, 10]); // return 1. You can choose:
                               //   - The first, second, and third points
detectSquares.count([14, 8]);  // return 0. The query point cannot form a square with any points in the data structure.
detectSquares.add([11, 2]);    // Adding duplicate points is allowed.
detectSquares.count([11, 10]); // return 2. You can choose:
                               //   - The first, second, and third points
                               //   - The first, third, and fourth points

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a simple List to store all the points as they are added. While the add operation is very fast, the count operation is less efficient because it requires searching through the list to find the necessary points to form a square.

Algorithm

  1. add(int[] point)

    • Add the point to a List<int[]> points.

  2. count(int[] point)

    • Let the query point be p1 = (x1, y1).
    • Create a HashSet of unique points from the points list to iterate over.
    • Initialize total_squares = 0.
    • For each unique point p4 = (x4, y4) in the hash set:
      • Check if p4 is a valid diagonal to p1: x1 != x4, y1 != y4, and abs(x1 - x4) == abs(y1 - y4).
      • If it is not a valid diagonal, continue to the next unique point.
      • If it is a valid diagonal, the other two corners are p2 = (x1, y4) and p3 = (x4, y1).
      • Count the occurrences of p2, p3, and p4 in the points list. Let these counts be c2, c3, and c4 respectively. This requires three separate traversals of the list for each unique diagonal.
      • Add the product c2 * c3 * c4 to total_squares.
    • Return total_squares.

Walkthrough

Data Structure

A java.util.List<int[]> is used to store all points, including duplicates.

add(point) Operation

The add operation is straightforward: the new point is simply appended to the end of the list. This is an O(1) operation.

count(point) Operation

The count operation relies on a geometric property of axis-aligned squares. Given a query point p1, any other point p4 can form a square with p1 only if it's a diagonal corner. This means p1 and p4 must have different x and y coordinates, and the absolute difference of their x-coordinates must equal the absolute difference of their y-coordinates.

The algorithm works as follows:

  1. To avoid redundant calculations for duplicate points, we first create a HashSet of unique points from our list.
  2. We iterate through each unique point p4 from this set.
  3. For each p4, we check if it can form a valid diagonal with the query point p1.
  4. If it's a valid diagonal, we can determine the coordinates of the other two required corners, p2 and p3.
  5. The crucial, and time-consuming, step is to then iterate through the entire original list to count the occurrences of p2, p3, and p4.
  6. The number of squares that can be formed with this specific diagonal configuration is the product of these counts: count(p2) * count(p3) * count(p4).
  7. We sum these products for all valid unique diagonals to get the final answer.
import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Objects; class DetectSquares {    private static class Point {        int x, y;        Point(int x, int y) { this.x = x; this.y = y; }        @Override        public boolean equals(Object o) {            if (this == o) return true;            if (o == null || getClass() != o.getClass()) return false;            Point point = (Point) o;            return x == point.x && y == point.y;        }        @Override        public int hashCode() { return Objects.hash(x, y); }    }     List<Point> points;     public DetectSquares() {        points = new ArrayList<>();    }        public void add(int[] point) {        points.add(new Point(point[0], point[1]));    }        public int count(int[] point) {        Point p1 = new Point(point[0], point[1]);        int totalSquares = 0;         HashSet<Point> uniquePoints = new HashSet<>(points);         for (Point p4 : uniquePoints) {            if (p1.x == p4.x || p1.y == p4.y || Math.abs(p1.x - p4.x) != Math.abs(p1.y - p4.y)) {                continue;            }             Point p2 = new Point(p1.x, p4.y);            Point p3 = new Point(p4.x, p1.y);             long count2 = 0, count3 = 0, count4 = 0;            for (Point p : points) {                if (p.equals(p2)) count2++;                if (p.equals(p3)) count3++;                if (p.equals(p4)) count4++;            }            totalSquares += count2 * count3 * count4;        }        return totalSquares;    }}

Complexity

Time

`add(point)`: `O(1)` `count(point)`: `O(M * N)`, where `N` is the total number of points added and `M` is the number of unique points. In the worst case where all points are unique (`M=N`), the complexity is `O(N^2)`. This can be too slow if the number of `count` calls is high or `N` is large.

Space

`O(N)` to store all the points in the list. The `count` method temporarily uses an additional `O(M)` space for the `HashSet` of unique points, where `N` is the total number of points and `M` is the number of unique points.

Trade-offs

Pros

  • The add operation is very fast, O(1).

  • The implementation is relatively straightforward to understand.

Cons

  • The count operation is inefficient, with a time complexity of O(N^2) in the worst case.

  • Repeatedly scanning the list to count points is computationally expensive.

  • Requires extra space for the HashSet within the count method.

Solutions

class DetectSquares { private Map < Integer , Map < Integer , Integer >> cnt = new HashMap <>(); public DetectSquares () { } public void add ( int [] point ) { int x = point [ 0 ], y = point [ 1 ]; cnt . computeIfAbsent ( x , k -> new HashMap <>()). merge ( y , 1 , Integer: : sum ); } public int count ( int [] point ) { int x1 = point [ 0 ], y1 = point [ 1 ]; if (! cnt . containsKey ( x1 )) { return 0 ; } int ans = 0 ; for ( var e : cnt . entrySet ()) { int x2 = e . getKey (); if ( x2 != x1 ) { int d = x2 - x1 ; var cnt1 = cnt . get ( x1 ); var cnt2 = e . getValue (); ans += cnt2 . getOrDefault ( y1 , 0 ) * cnt1 . getOrDefault ( y1 + d , 0 ) * cnt2 . getOrDefault ( y1 + d , 0 ); ans += cnt2 . getOrDefault ( y1 , 0 ) * cnt1 . getOrDefault ( y1 - d , 0 ) * cnt2 . getOrDefault ( y1 - d , 0 ); } } return ans ; } } /** * Your DetectSquares object will be instantiated and called as such: * DetectSquares obj = new DetectSquares(); * obj.add(point); * int param_2 = obj.count(point); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem