Detect Squares

LeetCode 2013: Detect Squares Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a frequency map (or 2D array) to store point counts, allowing us to iterate through a single diagonal point and mathematically calculate the positions of the other two corners in $O(1)$ time.

You are given a stream of 2D coordinates $(x, y)$. You need to design a data structure that supports two operations:

1. Add: Insert a point into the collection. Duplicate points are distinct and allowed.
2. Count: Given a query point, calculate how many sets of three existing points can form an axis-aligned square with the query point.

An axis-aligned square means the sides are parallel to the X and Y axes. The square must have a positive area (side length $> 0$).

This is a popular interview question, often referred to as the LeetCode 2013 Solution, testing your ability to optimize geometric lookups using hash maps or frequency arrays.

Brute Force Approach for Detect Squares

The naive approach focuses on the requirement to "choose three points." A direct translation of this requirement involves iterating through every possible triplet of points currently stored in the data structure.

For a query point $Q$:

1. Iterate through every point $P_1$ in the list.
2. Iterate through every point $P_2$ in the list ($P_2 \neq P_1$).
3. Iterate through every point $P_3$ in the list ($P_3 \neq P_2, P_3 \neq P_1$).
4. Check if points $\{Q, P_1, P_2, P_3\}$ form a valid axis-aligned square.

Pseudo-code:

function count(query_point):
    count = 0
    for p1 in points:
        for p2 in points:
            for p3 in points:
                if isSquare(query_point, p1, p2, p3):
                    count++
    return count

Why it fails: The time complexity for the count operation is $O(N^3)$, where $N$ is the number of points added so far. With up to 3000 operations, $N$ can grow to 3000. $3000^3$ is $2.7 \times 10^{10}$, which far exceeds the typical operations limit (usually around $10^8$) and results in a Time Limit Exceeded (TLE).

Algorithm Strategy: Design Patterns

We will maintain two data structures to balance the needs of iteration and lookup:

1. List of Points: To iterate through potential diagonal candidates efficiently.
2. Frequency Map (or 2D Grid): To perform $O(1)$ lookups for the existence and count of the "missing" corners.

The add Strategy: When a point is added, we increment its count in the frequency map and append it to the list of points.

The count Strategy:

1. We receive a query point $(qx, qy)$.
2. We iterate through the List of Points. Let the current point be $(px, py)$.
3. We check if $(px, py)$ can form a diagonal with $(qx, qy)$:
   • Condition: $|qx - px| == |qy - py|$ AND $qx \neq px$.
4. If valid, the other two required points are $Corner_A = (qx, py)$ and $Corner_B = (px, qy)$.
5. We look up the counts of $Corner_A$ and $Corner_B$ in our Frequency Map.
6. The number of ways to form this specific square using $(px, py)$ as the diagonal is count(Corner_A) * count(Corner_B).
7. Sum this product into the total result.

Note: Since we iterate through the list of all added points (including duplicates), we do not multiply by the count of $(px, py)$ itself. Each instance of $(px, py)$ in the list contributes to the sum individually.

Execution Flow

Let's trace add([3, 10]), add([11, 2]), add([3, 2]), and then count([11, 10]).

1. Initialize:

   • counts map is empty.
   • points list is empty.

2. add([3, 10]):

   • counts[3][10] becomes 1.
   • points list: [[3, 10]].

3. add([11, 2]):

   • counts[11][2] becomes 1.
   • points list: [[3, 10], [11, 2]].

4. add([3, 2]):

   • counts[3][2] becomes 1.
   • points list: [[3, 10], [11, 2], [3, 2]].

5. count([11, 10]): Query Point $Q = (11, 10)$.

   • Iterate points:
     • Point $P_1 = (3, 10)$:
       • $|11 - 3| = 8$, $|10 - 10| = 0$. Not equal. Not a diagonal.
     • Point $P_2 = (11, 2)$:
       • $|11 - 11| = 0$, $|10 - 2| = 8$. Not equal. Not a diagonal.
     • Point $P_3 = (3, 2)$:
       • $|11 - 3| = 8$.
       • $|10 - 2| = 8$.
       • Equal! This is a valid diagonal.
       • Missing corners: $(qx, py) = (11, 2)$ and $(px, qy) = (3, 10)$.
       • Lookup: counts[11][2] = 1, counts[3][10] = 1.
       • Add to total: $1 \times 1 = 1$.
   • Return: 1.

Proof of Correctness

The algorithm relies on the geometric property that a square is uniquely defined by a diagonal pair of vertices, provided the sides are axis-aligned.

For any query point $Q$ and existing point $P$, if they form the diagonal of an axis-aligned square, the other two vertices $A$ and $B$ are uniquely determined by the projections of $Q$ and $P$ onto the axes. Specifically, $A$ shares $Q$'s x-coordinate and $P$'s y-coordinate, while $B$ shares $P$'s x-coordinate and $Q$'s y-coordinate.

By summing count(A) * count(B) for every valid $P$ in our stream, we account for every combination of points that can complete the square. Since we iterate through the list of added points, duplicate points at position $P$ are handled naturally (each instance is processed).

Pattern Reuse Notes

The Design (General/Specific) pattern is fundamental for problems requiring custom data structure behavior.

• LeetCode 146: LRU Cache: Uses a HashMap for $O(1)$ access combined with a Doubly Linked List for $O(1)$ updates, balancing two operations like Detect Squares balances storage and lookup.
• LeetCode 155: Min Stack: Maintains auxiliary state (min values) parallel to the main data, similar to how we maintain counts parallel to the point list.
• LeetCode 225: Implement Stack using Queues: Requires manipulating standard structures to achieve specific API constraints.
• LeetCode 232: Implement Queue using Stacks: Similar to the above, focusing on efficient data movement to satisfy interface requirements.

Reference Implementation

C++ Solution for LeetCode 2013

1class DetectSquares {
2private:
3    // 2D array for O(1) access to point frequencies.
4    // Constraints are small (0 <= x, y <= 1000), so this is efficient.
5    int counts[1001][1001];
6    
7    // List to store all points for iteration during count()
8    vector<pair<int, int>> points;
9
10public:
11    DetectSquares() {
12        // Initialize the frequency array to 0
13        memset(counts, 0, sizeof(counts));
14    }
15    
16    void add(vector<int> point) {
17        int x = point[0];
18        int y = point[1];
19        
20        // Update frequency and store point
21        counts[x][y]++;
22        points.push_back({x, y});
23    }
24    
25    int count(vector<int> point) {
26        int qx = point[0];
27        int qy = point[1];
28        int totalSquares = 0;
29        
30        // Iterate through all existing points to find potential diagonals
31        for (const auto& p : points) {
32            int px = p.first;
33            int py = p.second;
34            
35            // Check for non-zero area square logic
36            // |qx - px| must equal |qy - py| and they cannot be the same point
37            if (abs(qx - px) != abs(qy - py) || qx == px) {
38                continue;
39            }
40            
41            // If (px, py) is the diagonal, the other two corners must be:
42            // (qx, py) and (px, qy)
43            totalSquares += counts[qx][py] * counts[px][qy];
44        }
45        
46        return totalSquares;
47    }
48};

Java Solution for LeetCode 2013

1class DetectSquares {
2    // 2D array to store frequency of each point
3    private int[][] counts;
4    // List to keep track of added points for iteration
5    private List<int[]> points;
6
7    public DetectSquares() {
8        counts = new int[1001][1001];
9        points = new ArrayList<>();
10    }
11    
12    public void add(int[] point) {
13        int x = point[0];
14        int y = point[1];
15        
16        counts[x][y]++;
17        points.add(point);
18    }
19    
20    public int count(int[] point) {
21        int qx = point[0];
22        int qy = point[1];
23        int ans = 0;
24        
25        // Iterate through all existing points to treat them as potential diagonals
26        for (int[] p : points) {
27            int px = p[0];
28            int py = p[1];
29            
30            // Condition 1: Must form a square (diff in x == diff in y)
31            // Condition 2: Area must be positive (qx != px)
32            if (Math.abs(qx - px) != Math.abs(qy - py) || qx == px) {
33                continue;
34            }
35            
36            // The other two corners are determined by geometry:
37            // Corner 1: (qx, py) -> Same X as query, Same Y as diagonal point
38            // Corner 2: (px, qy) -> Same X as diagonal point, Same Y as query
39            ans += counts[qx][py] * counts[px][qy];
40        }
41        
42        return ans;
43    }
44}

Python Solution for LeetCode 2013

1class DetectSquares:
2
3    def __init__(self):
4        # Dictionary to store frequency of points: (x, y) -> count
5        self.counts = defaultdict(int)
6        # List to store points for iteration
7        self.points = []
8
9    def add(self, point: List[int]) -> None:
10        x, y = point
11        self.counts[(x, y)] += 1
12        self.points.append((x, y))
13
14    def count(self, point: List[int]) -> int:
15        qx, qy = point
16        ans = 0
17        
18        # Iterate through all stored points
19        for px, py in self.points:
20            # Check if (px, py) can form a diagonal with (qx, qy)
21            # Must satisfy |dx| == |dy| and not be the same point
22            if abs(qx - px) != abs(qy - py) or qx == px:
23                continue
24            
25            # Identify the other two corners
26            # Corner 1: (qx, py)
27            # Corner 2: (px, qy)
28            ans += self.counts[(qx, py)] * self.counts[(px, qy)]
29            
30        return ans