Detect Squares

Medium
2074.

Detect Squares

Detect Squares is a medium coding problem on arrays, hash table and counting, asked in Google interviews.

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 point point = [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 == 2
  • 0 <= x, y <= 1000
  • At most 3000 calls are made to add and count in total
  • So every answer is below (3000 / 3)^3 = 10^9 and fits a signed 32-bit integer
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var DetectSquares = function() {
    
};

/**
 * @param {number[]} point
 * @return {void}
 */
DetectSquares.prototype.add = function(point) {
    
};

/**
 * @param {number[]} point
 * @return {number}
 */
DetectSquares.prototype.count = function(point) {
    
};

Sign in to run your own test cases

Sign in

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 point point = [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 == 2
  • 0 <= x, y <= 1000
  • At most 3000 calls are made to add and count in total
  • So every answer is below (3000 / 3)^3 = 10^9 and fits a signed 32-bit integer

Hints for Detect Squares

  1. Hint 1

    A square is fixed by two opposite corners. Given the query point, which added point should you guess?

  2. 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.

  3. Hint 3

    The other two corners are then (x, py) and (px, y). Keep a count per point in a hash map; each diagonal contributes count(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

  1. add([x, y]): increment cnt[(x, y)]; remember the point in a list of distinct points the first time it appears.
  2. count([x, y]): for every distinct point (px, py) with px != x and |px - x| == |py - y|, add cnt[(px, py)] · cnt[(x, py)] · cnt[(px, y)].
  3. 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 != x is 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 res

Java

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