Detect Squares — Solution in Python, Java & C++
Detect Squares solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Google.
Detect Squares is a medium coding problem on arrays, hash table and counting, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Counting
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Points on a grid arrive one at a time; the same point may be added many times, and each copy counts separately.
Write the class DetectSquares:
DetectSquares()starts with no points.void add(int[] point)adds the pointpoint = [x, y].int count(int[] point)returns the number of ways to choose three added points that, together with the query point, form an axis-aligned square with positive area (sides parallel to the axes). Copies of a point are different choices.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
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: With (3,10), (11,2) and (3,2), the query (11,10) closes one square of side 8. No square has (14,8) as a corner. After (11,2) is added a second time there are two ways to choose the three points.
Example 2
Input: ["DetectSquares","add","add","add","add","add","count"]
[[],[[1,1]],[[1,2]],[[2,1]],[[0,1]],[[1,0]],[[2,2]]]
Output: [null,null,null,null,null,null,1]
Explanation: Only the unit square with corners (1,1), (1,2), (2,1) and (2,2) uses the query point; (0,1) and (1,0) form no square with it.
Constraints
point.length == 20 <= x, y <= 1000At most 3000 calls are made to add and count in totalSo every answer is below (3000 / 3)^3 = 10^9 and fits a signed 32-bit integer
Hints for Detect Squares
Hint 1
A square is fixed by two opposite corners. Given the query point, which added point should you guess?
Hint 2
Try every distinct added point
(px, py)as the corner diagonal to the query(x, y): it must satisfy|px - x| == |py - y| != 0.Hint 3
The other two corners are then
(x, py)and(px, y). Keep a count per point in a hash map; each diagonal contributescount(px, py) · count(x, py) · count(px, y)ways.
How to solve Detect Squares
Count every point's copies in a hash map. For a query, each possible diagonal corner determines the whole square, and the number of ways is the product of the three corners' counts.
Approach
add([x, y]): incrementcnt[(x, y)]; remember the point in a list of distinct points the first time it appears.count([x, y]): for every distinct point(px, py)withpx != xand|px - x| == |py - y|, addcnt[(px, py)] · cnt[(x, py)] · cnt[(px, y)].- Return the sum.
Why it works
In an axis-aligned square the query's opposite corner differs from it by the same non-zero amount in both coordinates, and the remaining corners share one coordinate with each — so every square is found exactly once, through its diagonal corner. Choosing one copy of each of the three corners independently gives the product of their counts; a missing corner contributes 0.
Complexity
- Time —
O(1) per add, O(d) per count for d distinct points - Space —
O(d)
Pitfalls
px != xis needed: a diagonal with zero offset would be a square of area 0.- Iterate distinct points with their counts, not every added copy — otherwise copies are counted twice over.
- Squares must be axis-aligned; tilted squares do not count.
Reference solution
Python
class DetectSquares:
def __init__(self):
self.cnt = {}
def add(self, point: List[int]) -> None:
p = (point[0], point[1])
self.cnt[p] = self.cnt.get(p, 0) + 1
def count(self, point: List[int]) -> int:
x, y = point
cnt, res = self.cnt, 0
for (px, py), c in cnt.items(): # (px, py) as the corner opposite the query
if px != x and abs(px - x) == abs(py - y):
res += c * cnt.get((x, py), 0) * cnt.get((px, y), 0)
return resJava
class DetectSquares {
private HashMap<Integer, Integer> cnt = new HashMap<>(); // x * 1001 + y -> copies
public DetectSquares() {
}
public void add(int[] point) {
cnt.merge(point[0] * 1001 + point[1], 1, Integer::sum);
}
public int count(int[] point) {
int x = point[0], y = point[1], res = 0;
for (Map.Entry<Integer, Integer> e : cnt.entrySet()) { // (px, py) as the corner opposite the query
int px = e.getKey() / 1001, py = e.getKey() % 1001;
if (px != x && Math.abs(px - x) == Math.abs(py - y))
res += e.getValue() * cnt.getOrDefault(x * 1001 + py, 0) * cnt.getOrDefault(px * 1001 + y, 0);
}
return res;
}
}C++
class DetectSquares {
unordered_map<int, int> cnt; // x * 1001 + y -> copies
int get(int x, int y) {
auto it = cnt.find(x * 1001 + y);
return it == cnt.end() ? 0 : it->second;
}
public:
DetectSquares() {}
void add(vector<int> point) {
cnt[point[0] * 1001 + point[1]]++;
}
int count(vector<int> point) {
int x = point[0], y = point[1], res = 0;
for (auto& e : cnt) { // (px, py) as the corner opposite the query
int px = e.first / 1001, py = e.first % 1001;
if (px != x && abs(px - x) == abs(py - y)) res += e.second * get(x, py) * get(px, y);
}
return res;
}
};JavaScript
var DetectSquares = function() {
this.cnt = new Map(); // x * 1001 + y -> copies
};
DetectSquares.prototype.add = function(point) {
var k = point[0] * 1001 + point[1];
this.cnt.set(k, (this.cnt.get(k) || 0) + 1);
};
DetectSquares.prototype.count = function(point) {
var x = point[0], y = point[1], cnt = this.cnt, res = 0;
cnt.forEach(function(c, k) { // (px, py) as the corner opposite the query
var px = Math.floor(k / 1001), py = k % 1001;
if (px !== x && Math.abs(px - x) === Math.abs(py - y))
res += c * (cnt.get(x * 1001 + py) || 0) * (cnt.get(px * 1001 + y) || 0);
});
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets