2013. Detect Squares

MediumDesignArrayHash TableCounting

Problem Description

In this problem, you are tasked with managing a collection of points on the Cartesian coordinate system and determining how many distinct squares can be formed with any given query point as one of the corners. The squares of interest must have sides that are aligned with the X and Y axes, which means their sides are either horizontal or vertical, and no rotation is allowed. Additionally, these squares must have a positive area, so the sides need to have a non-zero length.

The operations you have to implement are:

Adding new points to a collection, even if they are duplicates of existing points.
For a given query point, counting the number of ways to select three other points from the collection such that together with the query point, they form a proper axis-aligned square.

You are effectively designing a class named DetectSquares that should support these operations. The class will have an add method to include new points into a data structure and a count method to find the number of squares with the query point.

Intuition

The essence of the solution is to find groups of three points in the current collection of points that, along with a given query point, can create an axis-aligned square. Focusing on the constraints of an axis-aligned square, we understand that for any two points that form a side of such a square, their X-coordinates or Y-coordinates must be the same, spelling out a straight horizontal or vertical line.

To arrive at the solution:

We need an efficient way to store the points and their frequencies (because duplicates are allowed and treated as different points). A dictionary of counters serves this purpose: a dictionary where each key is an X-coordinate and its value is a counter that keeps track of the number and frequency of Y-coordinates that appear at this X-coordinate.
Adding a new point involves inserting the point into the dictionary or updating the count if it's already there.
When counting the number of ways to form a square with a given point as one of its corners, you need to iterate over all points that could potentially be on the corners of squares that can be formed with the query point. Essentially, for each point with the same Y-coordinate as the query point but a different X-coordinate (forming a potential side of a square along the X-axis), check if there are points above and below (or at the opposite side on the same level) that could complete the square.
This can be visualized by examining the vertical and horizontal lines from the query point, calculating the potential side length of a square, and then looking for points that would form the opposite corners of the square, thus completing it.
The total count is the sum of all legitimate squares that can be formed with the query point and the points in the structure, considering all possible distances and directions (up and down from the query point).

By implementing a class with these functionalities, we can efficiently track points and count the squares formed with any given query point.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Solution Approach

The algorithm utilizes a combination of hash tables and arithmetic to efficiently solve the problem at hand. Below is a breakdown of the strategy using the various components within the solution code.

Data Structure Selection

A defaultdict of Counter objects is selected to maintain the frequency of points at different coordinates. This nested data structure is optimal because it allows:

O(1) average time complexity for adding points.
O(1) average time complexity for lookups.
The inner Counter keeps track of multiple Y-coordinates associated with a single X-coordinate.

`add` Method Implementation

When adding a point (x, y), the method updates the counter for the specified X-coordinate with the Y-coordinate. The Counter object efficiently keeps track of the number of times the same point is added.

1def add(self, point: List[int]) -> None:
2    x, y = point
3    self.cnt[x][y] += 1

`count` Method Implementation

Counting the number of squares is more complex. We execute the following steps:

Retrieve the X and Y coordinates of the query point.
If the X-coordinate of the query point is absent from our data structure, it cannot form a square, so we return 0.
Iterate over all stored X-coordinates, excluding the X-coordinate of the query point.
Calculate the potential side length d of the square as the difference between the current X-coordinate and the query's X-coordinate.
Count the squares by using the formula:

1self.cnt[x2][y1] * self.cnt[x1][y1 + d] * self.cnt[x2][y1 + d]

This formula checks for a point on the same Y-coordinate as the query but at a different X (self.cnt[x2][y1]), and then looks for points that can form the opposite corners of the square (self.cnt[x1][y1 + d] and self.cnt[x2][y1 + d]).

The same calculation is done for a potential square below the query point. This involves a similar calculation, but we subtract d from y1 to form the lower side of the square.

1def count(self, point: List[int]) -> int:
2    x1, y1 = point
3    if x1 not in self.cnt:
4        return 0
5    ans = 0
6    for x2 in self.cnt.keys():
7        if x2 != x1:
8            d = x2 - x1
9            ans += self.cnt[x2][y1] * self.cnt[x1][y1 + d] * self.cnt[x2][y1 + d]
10            ans += self.cnt[x2][y1] * self.cnt[x1][y1 - d] * self.cnt[x2][y1 - d]
11    return ans

The method iterates through all X-coordinates (except the query's X-coordinate), for each trying both upward and downward distances, and multiplies the corresponding point frequencies, thereby counting the number of valid squares that can be formed at that potential side length.

The total sum ans is accumulated and returned as the final count.

Conclusion

The solution leverages the constant-time lookups of hash tables and combines it with simple coordinate arithmetic to efficiently handle a stream of points and queries. This balance of data structure choice and algorithm ensures scalability with respect to a high number of points and queries.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Consider a DetectSquares class instance. Initially, there are no points in our collection. Let's walk through a small example of adding points and querying the number of possible squares.

Assume we add the points (1, 1), (1, 2), and (2, 1) to the collection by calling the add method for each point.

After adding these points, our data structure looks something like this:
```
1{
2  1: Counter({1: 1, 2: 1}),
3  2: Counter({1: 1})
4}
```
This reflects that we have points at (1, 1), (1, 2), and (2, 1) with each point occurring exactly once.

Now, add another point to the collection: (2, 2). The updated data structure becomes:

1{
2  1: Counter({1: 1, 2: 1}),
3  2: Counter({1: 1, 2: 1})
4}

We have added point (2, 2), and our coordinates are symmetric about point (1, 1) and (2, 2).

If we query with the point (1, 1) using the count method, we perform the following:

Retrieve the x and y coordinates of the query point, which are (x1, y1) = (1, 1).

Iterate over all stored x-coordinates (we have x = 1 and x = 2 in our data structure):

For x = 2:
- Calculate the potential side length d as the difference in x-coordinates, which is 2 - 1 = 1.
- Check for point at (2, 1), which is the point on the same y-coordinate but a different x-coordinate.
- Check for points at (1, 1 + d) = (1, 2) and (2, 1 + d) = (2, 2), which are potential opposite corners of a square with side length d.
- The number of squares for this side length can be counted as self.cnt[x2][y1] * self.cnt[x1][y1 + d] * self.cnt[x2][y1 + d] = 1 * 1 * 1 = 1.
- Since the square must have positive area, we don't consider squares below the query point because (1, 1 - d) = (1, 0) does not exist in our data structure.
The total number of squares with the query point (1, 1) as a corner is 1.

The described method accurately counts the squares with sides parallel to the x and y axes without rotating the points, considering both potential squares above and below the queried point (if applicable). This makes it efficient and reliable for rapidly answering multiple queries after incremental additions to the point collection.

Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Python Solution

1from collections import defaultdict
2
3class DetectSquares:
4    def __init__(self):
5        # Initialize a dictionary where each key is an x-coordinate that maps to a Counter 
6        # which holds y-coordinates and their corresponding counts.
7        self.coord_count = defaultdict(Counter)
8
9    def add(self, point: List[int]) -> None:
10        # Add a point to the collection. The point is a list of two integers [x, y].
11        x, y = point
12        # Increment the count of the point in the corresponding x's Counter by 1.
13        self.coord_count[x][y] += 1
14
15    def count(self, point: List[int]) -> int:
16        # Count how many squares can be formed with the given point as one of the vertices.
17        # The point is a list of two integers [x, y].
18        x1, y1 = point
19        # If the x-coordinate of the given point isn't in our record, return 0 because no squares can be formed.
20        if x1 not in self.coord_count:
21            return 0
22
23        total_squares = 0  # Initialize the number of squares to 0.
24      
25        # Iterate over all the unique x-coordinates in our dictionary.
26        for x2 in self.coord_count.keys():
27            # We need two distinct x-coordinates for a square (the length of the square side).
28            if x2 != x1:
29                # Compute the side length of the potential square.
30                d = x2 - x1
31                # Check for the top right and bottom right points of the square.
32                total_squares += self.coord_count[x2][y1] * self.coord_count[x1][y1 + d] * self.coord_count[x2][y1 + d]
33                # Check for the top left and bottom left points of the square if the y-axis distance is within bounds.
34                total_squares += self.coord_count[x2][y1] * self.coord_count[x1][y1 - d] * self.coord_count[x2][y1 - d]
35      
36        # Return the total number of squares found.
37        return total_squares
38
39# Usage example
40# obj = DetectSquares()
41# obj.add(point)
42# param_2 = obj.count(point)
43

Java Solution

1import java.util.HashMap;
2import java.util.Map;
3
4public class DetectSquares {
5    // Using a map of maps to store the count of points. The outer map's key is the x-coordinate,
6    // and the value is another map where the key is the y-coordinate and the value is the count of points.
7    private Map<Integer, Map<Integer, Integer>> pointCounts = new HashMap<>();
8
9    public DetectSquares() {
10        // Constructor doesn't need to do anything as the pointCounts map is initialized on declaration.
11    }
12
13    // Adds a new point to our data structure.
14    public void add(int[] point) {
15        int x = point[0];
16        int y = point[1];
17        // If x is not already a key in pointCounts, initialize it with an empty HashMap.
18        // Increase the count of the (x, y) point by 1, summing with the current count if it already exists.
19        pointCounts.computeIfAbsent(x, k -> new HashMap<>()).merge(y, 1, Integer::sum);
20    }
21
22    // Counts how many ways there are to form a square with one vertex being the given point.
23    public int count(int[] point) {
24        int x1 = point[0];
25        int y1 = point[1];
26      
27        // If there are no points with the same x-coordinate as point, return 0 since no square is possible.
28        if (!pointCounts.containsKey(x1)) {
29            return 0;
30        }
31      
32        int totalSquares = 0;
33
34        // Loop over all entries in the pointCounts.
35        for (Map.Entry<Integer, Map<Integer, Integer>> entry : pointCounts.entrySet()) {
36            int x2 = entry.getKey();
37            // We're not interested in points with the same x-coordinate as the given point (as we need a square).
38            if (x2 != x1) {
39                int d = x2 - x1; // Calculate the potential side length of the square.
40              
41                // Retrieve the counts maps for x1 and x2.
42                Map<Integer, Integer> yCountsForX1 = pointCounts.get(x1);
43                Map<Integer, Integer> yCountsForX2 = entry.getValue();
44              
45                // Calculate the number of squares that can be formed with the upper and lower horizontal points.
46                totalSquares += yCountsForX2.getOrDefault(y1, 0) * yCountsForX1.getOrDefault(y1 + d, 0) * yCountsForX2.getOrDefault(y1 + d, 0);
47                totalSquares += yCountsForX2.getOrDefault(y1, 0) * yCountsForX1.getOrDefault(y1 - d, 0) * yCountsForX2.getOrDefault(y1 - d, 0);
48            }
49        }
50        // Return the total number of squares found.
51        return totalSquares;
52    }
53}
54
55/**
56 * The code can be tested with following lines:
57 * DetectSquares obj = new DetectSquares();
58 * obj.add(point);
59 * int numberOfSquares = obj.count(point);
60 */
61

C++ Solution

1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class DetectSquares {
6public:
7    DetectSquares() {
8        // Constructor - no initialization is needed since the 'pointsCount' is default-initialized.
9    }
10
11    // Adds a new point to the data structure.
12    void add(vector<int> point) {
13        int x = point[0], y = point[1];
14        // Increment the count of how many times point (x, y) has been added.
15        pointsCount[x][y]++;
16    }
17
18    // Counts how many squares are there that contain the point as any of their corners.
19    int count(vector<int> point) {
20        int x1 = point[0], y1 = point[1];
21        // If no point has been added at this x-coordinate, no square can be formed.
22        if (!pointsCount.count(x1)) {
23            return 0;
24        }
25        int squaresCount = 0;
26        // Iterate over all different x-coordinates where we have points stored.
27        for (auto& [x2, yCountMap] : pointsCount) {
28            if (x2 != x1) {
29                // The side length of potential squares.
30                int d = x2 - x1;
31              
32                // Retrieve the count map for the current x1 coordinate.
33                auto& yCountMap1 = pointsCount[x1];
34              
35                // Calculate the number of squares with top right corner at (x2, y1).
36                squaresCount += yCountMap[y1] * yCountMap1[y1 + d] * yCountMap[y1 + d];
37              
38                // Calculate the number of squares with bottom right corner at (x2, y1).
39                // The condition (y1 > d) ensures that we do not access a negative y-coordinate.
40                if (y1 > d) {
41                    squaresCount += yCountMap[y1] * yCountMap1[y1 - d] * yCountMap[y1 - d];
42                }
43            }
44        }
45        return squaresCount;
46    }
47
48private:
49    // This unordered map stores for each x-coordinate (key),
50    // another unordered map with y-coordinate as key and point count as value.
51    unordered_map<int, unordered_map<int, int>> pointsCount;
52};
53
54/**
55 * The DetectSquares class is instantiated and member functions are called as such:
56 * DetectSquares* obj = new DetectSquares();
57 * obj->add(point);
58 * int numberOfSquares = obj->count(point);
59 * delete obj; // When done, delete the object to free memory.
60 */
61

Typescript Solution

1// TypeScript uses a map type called Map, replacing unordered_map from C++.
2const pointsCount = new Map<number, Map<number, number>>();
3
4// Adds a new point to the data structure.
5function add(point: number[]): void {
6    const [x, y] = point;
7    // If pointsCount does not have the x-coordinate, initialize it.
8    if (!pointsCount.has(x)) {
9        pointsCount.set(x, new Map<number, number>());
10    }
11    const yCountMap = pointsCount.get(x);
12    // Increment the count of how many times point (x, y) has been added.
13    const currentCount = yCountMap.get(y) || 0;
14    yCountMap.set(y, currentCount + 1);
15}
16
17// Counts how many squares are there that contain the point as any of their corners.
18function count(point: number[]): number {
19    const [x1, y1] = point;
20    // If no point has been added at this x-coordinate, no square can be formed.
21    if (!pointsCount.has(x1)) {
22        return 0;
23    }
24    let squaresCount = 0;
25  
26    // Iterate over all different x-coordinates where we have points stored.
27    pointsCount.forEach((yCountMap, x2) => {
28        if (x2 !== x1) {
29            // The side length of potential squares.
30            const d = x2 - x1;
31            const yCountMap1 = pointsCount.get(x1);
32
33            // Only proceed if the y-coordinate count map exists for x1.
34            if (yCountMap1) {
35                // Calculate the number of squares with top right corner at (x2, y1).
36                squaresCount += (yCountMap.get(y1) || 0) * (yCountMap1.get(y1 + d) || 0) * (yCountMap.get(y1 + d) || 0);
37              
38                // Calculate the number of squares with bottom right corner at (x2, y1).
39                // The condition (y1 > d) ensures that we do not access a negative y-coordinate.
40                if (y1 > d) {
41                    squaresCount += (yCountMap.get(y1) || 0) * (yCountMap1.get(y1 - d) || 0) * (yCountMap.get(y1 - d) || 0);
42                }
43            }
44        }
45    });
46
47    return squaresCount;
48}
49
50// Note: A TypeScript implementation would typically have these methods within a class. 
51// Defining them as globals is atypical and does not provide encapsulation or instance-specific data, 
52// as would be common in a proper TypeScript object-oriented design. 
53// However, based on the constraint, this is a global implementation.
54

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

Time and Space Complexity

Time Complexity

__init__ method: The initialization of the DetectSquares class sets up a default dictionary with a Counter as its default value. The time complexity for this operation is O(1) because it's a simple assignment operation.
add method: Adds a point with coordinates (x, y). This part has a time complexity of O(1) because it's just incrementing the count of the point (x, y) in a hash table, which is an O(1) operation.
count method: This calculates the number of squares with one corner at the given point. The method iterates through all unique x coordinates stored in the hash map (the keys of the cnt dictionary). For each x2 other than x1, it calculates two potential square sides (d = x2 - x1 for the side to the right of (x1, y1) and d = x1 - x2 for the side to the left of (x1, y1)). It then checks for points that are d distance away on the y-axis both above and below (x1,y1).
- For a given point, the number of potential squares is computed by considering each different x2 coordinate as a potential corner. If there are n different x coordinates, there could be up to n - 1 iterations (discounting the current x coordinate).
- Inside each iteration, the calculation ans += ... involves constant-time dictionary lookups and arithmetic operations. So each iteration can be considered O(1).
- Therefore, the time complexity for this method will be O(n), where n is the number of unique x coordinates stored so far when count is called.

The time complexity of the add method is insignificant compared to the count method which dominates when analyzing the complexity of the class operations. Hence, the overall time complexity hinges on the count method which is O(n) in the worst case.

Space Complexity

The space complexity of the DetectSquares class is dominated by the self.cnt dictionary, which stores the counts of points. This dictionary can potentially grow to include every unique point seen so far.
If the total number of points is p, and there are u unique x-coordinates and v unique y-coordinates amongst them, the maximum storage required would be for a complete mapping of these points, which is O(u * v).
In the worst-case scenario where every added point has a unique (x, y) combination, the space complexity would be O(p), where p is the number of add operations performed.

Therefore, the space complexity of the DetectSquares class is O(p).

Learn more about how to find time and space complexity quickly.

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2013. Detect Squares

Problem Description

Intuition

Solution Approach

Data Structure Selection

add Method Implementation

count Method Implementation

Conclusion

Example Walkthrough

Python Solution

Java Solution

`add` Method Implementation

`count` Method Implementation