# Detect Squares

Published: Dec 29, 2022

Medium Hash Table Counting Design

## Problem Description

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.

Constraints:

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

https://leetcode.com/problems/detect-squares/

## Examples

Example 1
Input
[[], [[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.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.count([11, 10]); // return 2. You can choose:
//   - The first, second, and third points
//   - The first, third, and fourth points

## How to Solve

This problem requires an effective way of finding sides of squares. Given the x, y coordinate, the first step is to find y coordinates whose x coordinate is the same. The length of a side is easily calculated by a difference of the y coordinates. Whether the supposed 3 points exist or not, multiply the counts of [x0, y], [x0 + side, y0], [x0 + side, y]. This will narrow down count to the what we want. Then, count for the other side, [x0, y], [x0 - side, y0], [x0 - side, y].

The solution here used a single hash table. It is a hash table of hash table and saves x to y counts.

The point here is what the hash table returns when the given key doesn’t exist. Python’s collections.defaultdict and collections.Counter return 0 when the value is integer. C++’s unordered_map also returns 0 when the value type is integer. However, some other languages or data structures need to specify the value when the key doesn’t exist. We should be careful about that.

## Solution

class DetectSquares {
private:
unordered_map<int, unordered_map<int, int>> x_coord;

public:
DetectSquares() {}

int x = point[0], y = point[1];
x_coord[x][y]++;
}

int count(vector<int> point) {
int x0 = point[0], y0 = point[1], result = 0;
for (auto &[y, cnt] : x_coord[x0]) {
if (y == y0) { continue; }
int side = y - y0;
result += cnt * x_coord[x0 + side][y0] * x_coord[x0 + side][y];
result += cnt * x_coord[x0 - side][y0] * x_coord[x0 - side][y];
}
return result;
}
};
import java.util.HashMap;
import java.util.Map;

public class DetectSquares {
private Map<Integer, Map<Integer, Integer>> x_coord = new HashMap<>();

public DetectSquares() {}

Map<Integer, Integer> y_coord = x_coord.getOrDefault(point[0], new HashMap<>());
int cnt = y_coord.getOrDefault(point[1], 0);
y_coord.put(point[1], cnt + 1);
x_coord.put(point[0], y_coord);
}

public int count(int[] point) {
int x0 = point[0], y0 = point[1], result = 0;
for (int y : x_coord.getOrDefault(x0, new HashMap<>()).keySet()) {
if (y == y0) { continue; }
int side = y - y0;
int cnt = x_coord.getOrDefault(x0, new HashMap<>()).getOrDefault(y, 0);
result += cnt *
x_coord.getOrDefault(x0 + side, new HashMap<>()).getOrDefault(y0, 0) *
x_coord.getOrDefault(x0 + side, new HashMap<>()).getOrDefault(y, 0);
result += cnt *
x_coord.getOrDefault(x0 - side, new HashMap<>()).getOrDefault(y0, 0) *
x_coord.getOrDefault(x0 - side, new HashMap<>()).getOrDefault(y, 0);
}
return result;
}
}
var DetectSquares = function() {
this.x_coord = new Map();
};

/**
* @param {number[]} point
* @return {void}
*/
const [x, y] = point;
let y_coord = this.x_coord.has(x) ? this.x_coord.get(x) : new Map();
let cnt = y_coord.has(y) ? y_coord.get(y) : 0;
y_coord.set(y, cnt + 1);
this.x_coord.set(x, y_coord);
};

/**
* @param {number[]} point
* @return {number}
*/
DetectSquares.prototype.count = function(point) {
const [x0, y0] = point;
let result = 0;
const y_coord = this.x_coord.has(x0) ? this.x_coord.get(x0) : new Map();
y_coord.forEach((cnt, y) => {
if (y == y0) { return; }
let side = y - y0;
if (this.x_coord.has(x0 + side)) {
let tmp1 = this.x_coord.get(x0 + side).has(y0) ? this.x_coord.get(x0 + side).get(y0) : 0;
let tmp2 = this.x_coord.get(x0 + side).has(y) ? this.x_coord.get(x0 + side).get(y) : 0;
result += cnt * tmp1 * tmp2;
}
if (this.x_coord.has(x0 - side)) {
let tmp1 = this.x_coord.get(x0 - side).has(y0) ? this.x_coord.get(x0 - side).get(y0) : 0;
let tmp2 = this.x_coord.get(x0 - side).has(y) ? this.x_coord.get(x0 - side).get(y) : 0;
result += cnt * tmp1 * tmp2;
}
});
return result;
};
class DetectSquares:

def __init__(self):
self.x_coord = collections.defaultdict(collections.Counter)

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

def count(self, point: List[int]) -> int:
x0, y0 = point
result = 0
for y in self.x_coord[x0]:
if y == y0: continue
side = y - y0
result += self.x_coord[x0][y] * self.x_coord[x0 + side][y0] * self.x_coord[x0 + side][y]
result += self.x_coord[x0][y] * self.x_coord[x0 - side][y0] * self.x_coord[x0 - side][y]
return result
class DetectSquares
def initialize()
@x_coord = Hash.new {|h0, k0| h0[k0] = Hash.new {|h1, k1| h1[k1] = 0}}
end

=begin
:type point: Integer[]
:rtype: Void
=end
x, y = point
@x_coord[x][y] += 1
end

=begin
:type point: Integer[]
:rtype: Integer
=end
def count(point)
x0, y0 = point
result = 0
@x_coord[x0].each do |y, cnt|
if y == y0
next
end
side = y - y0
result += cnt * @x_coord[x0 + side][y0] * @x_coord[x0 + side][y]
result += cnt * @x_coord[x0 - side][y0] * @x_coord[x0 - side][y]
end
result
end

end

## Complexities

• Time: add: O(1), count: O(n) – n: number of unique y coordinates of a single x coordinate
• Space: O(m) – m: number of unique x coordinates