In this guide, you will get 2013. Detect Squares LeetCode Solution with the best time and space complexity. The solution to Detect Squares problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Complexity Analysis
Time Complexity: O(|\texttt{add()}|)
Space Complexity: O(|\texttt{add()}|)
2013. Detect Squares LeetCode Solution in C++
class DetectSquares {
public:
void add(vector<int> point) {
++pointCount[getHash(point[0], point[1])];
}
int count(vector<int> point) {
const int x1 = point[0];
const int y1 = point[1];
int ans = 0;
for (const auto& [hash, count] : pointCount) {
const int x3 = hash >> 10;
const int y3 = hash & 1023;
if (x1 != x3 && abs(x1 - x3) == abs(y1 - y3)) {
const int p = getHash(x1, y3);
const int q = getHash(x3, y1);
if (pointCount.contains(p) && pointCount.contains(q))
ans += count * pointCount[p] * pointCount[q];
}
}
return ans;
}
private:
unordered_map<int, int> pointCount;
int getHash(int i, int j) {
return i << 10 | j;
}
}; /* code provided by PROGIEZ */
2013. Detect Squares LeetCode Solution in Java
class DetectSquares {
public void add(int[] point) {
pointCount.merge(getHash(point[0], point[1]), 1, Integer::sum);
}
public int count(int[] point) {
final int x1 = point[0];
final int y1 = point[1];
int ans = 0;
for (final int hash : pointCount.keySet()) {
final int count = pointCount.get(hash);
final int x3 = hash >> 10;
final int y3 = hash & 1023;
if (x1 != x3 && Math.abs(x1 - x3) == Math.abs(y1 - y3)) {
final int p = getHash(x1, y3);
final int q = getHash(x3, y1);
if (pointCount.containsKey(p) && pointCount.containsKey(q))
ans += count * pointCount.get(p) * pointCount.get(q);
}
}
return ans;
}
private Map<Integer, Integer> pointCount = new HashMap<>();
private int getHash(int i, int j) {
return i << 10 | j;
}
} // code provided by PROGIEZ
2013. Detect Squares LeetCode Solution in Python
class DetectSquares:
def __init__(self):
self.pointCount = collections.Counter()
def add(self, point: list[int]) -> None:
self.pointCount[tuple(point)] += 1
def count(self, point: list[int]) -> int:
x1, y1 = point
ans = 0
for (x3, y3), c in self.pointCount.items():
if x1 != x3 and abs(x1 - x3) == abs(y1 - y3):
ans += c * self.pointCount[(x1, y3)] * self.pointCount[(x3, y1)]
return ans # code by PROGIEZ
