2013. Detect Squares - Solution

Q: Is Detect Squares easy or hard?

Detect Squares is classified as a Medium problem on LeetCode. The implementation is straightforward once you recognize that every square can be identified by a diagonal pair and that point frequencies allow constant-time validation of the remaining corners.

Q: Detect Squares Python/Java solution

In Python or Java, store points in a hash map where the key represents the coordinate pair and the value is the count of occurrences. The add method increments the frequency, while the count method iterates through stored points and multiplies the frequencies of the required square corners.

Q: How to solve Detect Squares in O(n)?

Store every inserted point in a hash map with its frequency. For a query point (x, y), iterate through all points and treat (px, py) as a diagonal if |x − px| equals |y − py|. If valid, check the other two corners (x, py) and (px, y) in the map and multiply their frequencies. This gives an O(n) count operation.

Q: What is the best approach for Detect Squares?

The most practical solution uses a HashMap to store the frequency of each point. During a count query, iterate through stored points and treat each as a potential diagonal of a square. The other two required corners are checked with constant-time hash lookups. This results in O(1) add operations and O(n) time for each count query.

Q: Is Detect Squares asked at Google/Amazon/Meta?

Detect Squares is a common design-style geometry problem similar to questions asked at companies like Amazon and Meta. It tests the ability to combine hash tables with coordinate geometry and efficient counting logic in a custom data structure.

Q: What data structure is used in Detect Squares?

A hash table is the primary data structure used in the optimal solution. It stores frequencies of points keyed by their coordinates, enabling constant-time lookups when verifying the other two corners of a potential square.

Q: What is the time complexity of Detect Squares?

Using the HashMap frequency approach, the add operation runs in O(1) time and the count operation runs in O(n), where n is the number of stored points. Space complexity is O(n) because each unique coordinate pair is stored in the map.

The problem

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.

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

Approach overview

Problem Overview: You design a data structure that supports two operations: add(point) and count(point). After inserting multiple 2D points, the count query must return how many axis-aligned squares can be formed where the query point is one of the corners.

Approach 1: Use HashMap to Store Point Frequencies (Add: O(1), Count: O(n))

The core idea is to store how many times each point appears. Use a HashMap keyed by coordinates such as (x, y). When you call count(x, y), iterate through all stored points and treat each candidate point as the potential diagonal of a square. A valid diagonal must satisfy |x - px| == |y - py| and must not share the same row or column. Once you identify a diagonal, the other two corners are (x, py) and (px, y). Their frequencies are retrieved from the hash map, and the number of squares contributed by this diagonal is the product of their counts.

This works because an axis-aligned square is uniquely determined by a diagonal pair. The add operation simply increments the stored frequency for the point in O(1) time. The count operation scans all stored points, making it O(n) per query with O(n) space. This approach is flexible, handles duplicate points naturally, and relies on constant-time hash lookups. It heavily uses concepts from hash tables, data structure design, and coordinate-based counting.

Approach 2: Use Frequency Matrix (Add: O(1), Count: O(C))

Since the coordinate range in the problem is small (typically 0–1000), you can store point frequencies in a 2D matrix where freq[x][y] represents how many times a point was added. The add operation increments the cell directly. For the count query, iterate across all possible columns to locate potential square side lengths relative to the query point.

If the query point is (x, y), check candidate points on the same row such as (cx, y). The distance d = cx - x determines possible square positions above and below. The other required points become (x, y + d) and (cx, y + d), or the symmetric positions below the row. Multiply the stored frequencies of these three points to count how many squares exist. This approach runs in O(C) time per query where C is the coordinate range (about 1000) and uses O(C²) space.

Recommended for interviews: The HashMap frequency approach is the expected solution. It shows strong understanding of geometry constraints, frequency counting, and efficient array coordinate handling. Interviewers mainly care about recognizing that a square can be identified using a diagonal and that the remaining corners can be counted with constant-time lookups.

Approach 1: Use HashMap to Store Point Frequencies

This approach utilizes a hash map to store the frequency of points.

To add a point, simply increase its count in the map. To count squares, iterate over points that share the same x-coordinate or y-coordinate, calculate potential square corners, and update the count based on available points in the map.

Python

from collections import defaultdict

class DetectSquares:
    def __init__(self):
        self.point_count = defaultdict(lambda: defaultdict(int))

    def add(self, point):
        self.point_count[point[0]][point[1]] += 1

    def count(self, point):
        tx, ty = point
        total_count = 0

        for x in self.point_count:
            if x != tx:
                side_length = x - tx
                total_count += self.point_count[x][ty] * self.point_count[tx][ty + side_length] * self.point_count[x][ty + side_length]
                total_count += self.point_count[x][ty] * self.point_count[tx][ty - side_length] * self.point_count[x][ty - side_length]

        return total_count

Java

import java.util.HashMap;
import java.util.Map;

public class DetectSquares {
    private final Map<Integer, Map<Integer, Integer>> pointCount;

    public DetectSquares() {
        pointCount = new HashMap<>();
    }

    public void add(int[] point) {
        pointCount.putIfAbsent(point[0], new HashMap<>());
        pointCount.get(point[0]).put(point[1], pointCount.get(point[0]).getOrDefault(point[1], 0) + 1);
    }

    public int count(int[] point) {
        int tx = point[0], ty = point[1];
        int totalCount = 0;
        if (!pointCount.containsKey(tx)) return 0;
        for (Map.Entry<Integer, Map<Integer, Integer>> entry : pointCount.entrySet()) {
            int x = entry.getKey();
            if (x != tx) {
                int sideLength = x - tx;
                Map<Integer, Integer> col = entry.getValue();
                totalCount += col.getOrDefault(ty, 0) * pointCount.get(tx).getOrDefault(ty + sideLength, 0) * col.getOrDefault(ty + sideLength, 0);
                totalCount += col.getOrDefault(ty, 0) * pointCount.get(tx).getOrDefault(ty - sideLength, 0) * col.getOrDefault(ty - sideLength, 0);
            }
        }
        return totalCount;
    }
}

C++

#include <unordered_map>
#include <vector>
#include <utility>
using namespace std;

class DetectSquares {
public:
    unordered_map<int, unordered_map<int, int>> pointCount;

    void add(vector<int> point) {
        pointCount[point[0]][point[1]]++;
    }

    int count(vector<int> point) {
        int tx = point[0], ty = point[1];
        int totalCount = 0;
        for (auto& [x, col] : pointCount) {
            if (x != tx) {
                int sideLength = x - tx;
                totalCount += col[ty] * pointCount[tx][ty + sideLength] * col[ty + sideLength];
                totalCount += col[ty] * pointCount[tx][ty - sideLength] * col[ty - sideLength];
            }
        }
        return totalCount;
    }
};

JavaScript

class DetectSquares {
    constructor() {
        this.pointCount = new Map();
    }

    add(point) {
        const [x, y] = point;
        if (!this.pointCount.has(x)) {
            this.pointCount.set(x, new Map());
        }
        const row = this.pointCount.get(x);
        if (!row.has(y)) {
            row.set(y, 0);
        }
        row.set(y, row.get(y) + 1);
    }

    count(point) {
        const [tx, ty] = point;
        let totalCount = 0;

        for (const [x, col] of this.pointCount.entries()) {
            if (x !== tx) {
                const sideLength = x - tx;
                totalCount += (col.get(ty) || 0)
                             * (this.pointCount.get(tx).get(ty + sideLength) || 0)
                             * (col.get(ty + sideLength) || 0);
                totalCount += (col.get(ty) || 0)
                             * (this.pointCount.get(tx).get(ty - sideLength) || 0)
                             * (col.get(ty - sideLength) || 0);
            }
        }
        return totalCount;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_COORD 1001

typedef struct {
    int count[MAX_COORD][MAX_COORD];
} DetectSquares;

DetectSquares* detectSquaresCreate() {
    DetectSquares* obj = (DetectSquares*)malloc(sizeof(DetectSquares));
    memset(obj->count, 0, sizeof(obj->count));
    return obj;
}

void detectSquaresAdd(DetectSquares* obj, int* point, int pointSize) {
    int x = point[0], y = point[1];
    obj->count[x][y]++;
}

int detectSquaresCount(DetectSquares* obj, int* point, int pointSize) {
    int tx = point[0], ty = point[1];
    int totalCount = 0;
    for (int x = 0; x < MAX_COORD; x++) {
        if (x != tx) {
            int sideLength = abs(x - tx);
            if (ty + sideLength < MAX_COORD) {
                totalCount += obj->count[x][ty] * obj->count[tx][ty + sideLength] * obj->count[x][ty + sideLength];
            }
            if (ty - sideLength >= 0) {
                totalCount += obj->count[x][ty] * obj->count[tx][ty - sideLength] * obj->count[x][ty - sideLength];
            }
        }
    }
    return totalCount;
}

void detectSquaresFree(DetectSquares* obj) {
    free(obj);
}

using System;
using System.Collections.Generic;

public class DetectSquares {
    private readonly Dictionary<int, Dictionary<int, int>> pointCount;

    public DetectSquares() {
        pointCount = new Dictionary<int, Dictionary<int, int>>();
    }

    public void Add(int[] point) {
        if (!pointCount.ContainsKey(point[0])) {
            pointCount[point[0]] = new Dictionary<int, int>();
        }
        if (!pointCount[point[0]].ContainsKey(point[1])) {
            pointCount[point[0]][point[1]] = 0;
        }
        pointCount[point[0]][point[1]]++;
    }

    public int Count(int[] point) {
        int tx = point[0], ty = point[1];
        int totalCount = 0;
        foreach (var (x, col) in pointCount) {
            if (x != tx) {
                int sideLength = x - tx;
                if (col.ContainsKey(ty) && pointCount[tx].ContainsKey(ty + sideLength) && col.ContainsKey(ty + sideLength)) {
                    totalCount += col[ty] * pointCount[tx][ty + sideLength] * col[ty + sideLength];
                }
                if (col.ContainsKey(ty) && pointCount[tx].ContainsKey(ty - sideLength) && col.ContainsKey(ty - sideLength)) {
                    totalCount += col[ty] * pointCount[tx][ty - sideLength] * col[ty - sideLength];
                }
            }
        }
        return totalCount;
    }
}

This Python solution uses a defaultdict to handle default values and ease of use with nested dictionaries for points. Each x-coordinate holds a dictionary with counts of y-coordinates.

Complexity

Time Complexity: O(n) for iterating potential y-alignments.
Space Complexity: O(N) for tracking point counts.

Try this approach in the editor

Approach 2: Use Frequency Matrix

This approach uses a frequency matrix to store the occurrence of each point in a 2D array format. The solution is similar to the hash map solution but relies on direct index access for storing and querying point counts.

While this approach simplifies access patterns, it can incur significant space usage depending on input constraints.

Python

class DetectSquares:
    def __init__(self):
        self.point_freq = [[0] * 1001 for _ in range(1001)]

    def add(self, point):
        x, y = point
        self.point_freq[x][y] += 1

    def count(self, point):
        tx, ty = point
        total_count = 0

        for x in range(1001):
            if x != tx:
                side_length = abs(x - tx)
                if 0 <= ty + side_length < 1001:
                    total_count += self.point_freq[x][ty] * self.point_freq[tx][ty + side_length] * self.point_freq[x][ty + side_length]
                if 0 <= ty - side_length < 1001:
                    total_count += self.point_freq[x][ty] * self.point_freq[tx][ty - side_length] * self.point_freq[x][ty - side_length]

        return total_count

Java

public class DetectSquares {
    private final int[][] pointFreq = new int[1001][1001];

    public void add(int[] point) {
        pointFreq[point[0]][point[1]]++;
    }

    public int count(int[] point) {
        int tx = point[0], ty = point[1];
        int totalCount = 0;

        for (int x = 0; x < 1001; x++) {
            if (x != tx) {
                int sideLength = Math.abs(x - tx);
                if (ty + sideLength < 1001) {
                    totalCount += pointFreq[x][ty] * pointFreq[tx][ty + sideLength] * pointFreq[x][ty + sideLength];
                }
                if (ty - sideLength >= 0) {
                    totalCount += pointFreq[x][ty] * pointFreq[tx][ty - sideLength] * pointFreq[x][ty - sideLength];
                }
            }
        }
        return totalCount;
    }
}

C++

#include <vector>
using namespace std;

class DetectSquares {
private:
    int pointFreq[1001][1001] = {};
public:
    void add(vector<int> point) {
        pointFreq[point[0]][point[1]]++;
    }

    int count(vector<int> point) {
        int tx = point[0], ty = point[1];
        int totalCount = 0;
        for (int x = 0; x < 1001; ++x) {
            if (x != tx) {
                int sideLength = abs(x - tx);
                if (ty + sideLength < 1001) {
                    totalCount += pointFreq[x][ty] * pointFreq[tx][ty + sideLength] * pointFreq[x][ty + sideLength];
                }
                if (ty - sideLength >= 0) {
                    totalCount += pointFreq[x][ty] * pointFreq[tx][ty - sideLength] * pointFreq[x][ty - sideLength];
                }
            }
        }
        return totalCount;
    }
};

JavaScript

class DetectSquares {
    constructor() {
        this.pointFreq = Array.from({ length: 1001 }, () => new Array(1001).fill(0));
    }

    add(point) {
        const [x, y] = point;
        this.pointFreq[x][y]++;
    }

    count(point) {
        const [tx, ty] = point;
        let totalCount = 0;

        for (let x = 0; x < 1001; x++) {
            if (x !== tx) {
                const sideLength = x - tx;
                if (ty + sideLength < 1001) {
                    totalCount += this.pointFreq[x][ty] * this.pointFreq[tx][ty + sideLength] * this.pointFreq[x][ty + sideLength];
                }
                if (ty - sideLength >= 0) {
                    totalCount += this.pointFreq[x][ty] * this.pointFreq[tx][ty - sideLength] * this.pointFreq[x][ty - sideLength];
                }
            }
        }
        return totalCount;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_COORD 1001

typedef struct {
    int count[MAX_COORD][MAX_COORD];
} DetectSquares;

DetectSquares* detectSquaresCreate() {
    DetectSquares* obj = (DetectSquares*)malloc(sizeof(DetectSquares));
    memset(obj->count, 0, sizeof(obj->count));
    return obj;
}

void detectSquaresAdd(DetectSquares* obj, int* point, int pointSize) {
    int x = point[0], y = point[1];
    obj->count[x][y]++;
}

int detectSquaresCount(DetectSquares* obj, int* point, int pointSize) {
    int tx = point[0], ty = point[1];
    int totalCount = 0;
    for (int x = 0; x < MAX_COORD; x++) {
        if (x != tx) {
            int sideLength = abs(x - tx);
            if (ty + sideLength < MAX_COORD) {
                totalCount += obj->count[x][ty] * obj->count[tx][ty + sideLength] * obj->count[x][ty + sideLength];
            }
            if (ty - sideLength >= 0) {
                totalCount += obj->count[x][ty] * obj->count[tx][ty - sideLength] * obj->count[x][ty - sideLength];
            }
        }
    }
    return totalCount;
}

void detectSquaresFree(DetectSquares* obj) {
    free(obj);
}

public class DetectSquares
{
    private int[][] pointFreq;

    public DetectSquares()
    {
        pointFreq = new int[1001][];
        for (int i = 0; i < 1001; i++)
        {
            pointFreq[i] = new int[1001];
        }
    }

    public void Add(int[] point)
    {
        pointFreq[point[0]][point[1]]++;
    }

    public int Count(int[] point)
    {
        int tx = point[0], ty = point[1];
        int totalCount = 0;

        for (int x = 0; x < 1001; x++)
        {
            if (x != tx)
            {
                int sideLength = x - tx;
                if (ty + sideLength < 1001)
                {
                    totalCount += pointFreq[x][ty] * pointFreq[tx][ty + sideLength] * pointFreq[x][ty + sideLength];
                }
                if (ty - sideLength >= 0)
                {
                    totalCount += pointFreq[x][ty] * pointFreq[tx][ty - sideLength] * pointFreq[x][ty - sideLength];
                }
            }
        }
        return totalCount;
    }
}

The implementation in Python applies an index-access frequently matrix using list comprehensions, ensuring each coordinate pair is evaluated for potential square points through fixed-width looping.

Complexity

Time Complexity: O(n) for traversal and tally operations.
Space Complexity: O(1), due to static-bound array sizing.

Try this approach in the editor

Approach 3: Hash Table

We can use a hash table cnt to maintain all the information of the points, where cnt[x][y] represents the count of point (x, y).

When calling the add(x, y) method, we increase the value of cnt[x][y] by 1.

When calling the count(x_1, y_1) method, we need to get three other points to form an axis-aligned square. We can enumerate the point (x_2, y_1) that is parallel to the x-axis and at a distance d from (x_1, y_1). If such a point exists, based on these two points, we can determine the other two points as (x_1, y_1 + d) and (x_2, y_1 + d), or (x_1, y_1 - d) and (x_2, y_1 - d). We can add up the number of schemes for these two situations.

In terms of time complexity, the time complexity of calling the add(x, y) method is O(1), and the time complexity of calling the count(x_1, y_1) method is O(n); the space complexity is O(n). Here, n is the number of points in the data stream.

type DetectSquares struct {
	cnt map[int]map[int]int
}

func Constructor() DetectSquares {
	return DetectSquares{map[int]map[int]int{}}
}

func (this *DetectSquares) Add(point []int) {
	x, y := point[0], point[1]
	if _, ok := this.cnt[x]; !ok {
		this.cnt[x] = map[int]int{}
	}
	this.cnt[x][y]++
}

func (this *DetectSquares) Count(point []int) (ans int) {
	x1, y1 := point[0], point[1]
	if cnt1, ok := this.cnt[x1]; ok {
		for x2, cnt2 := range this.cnt {
			if x2 != x1 {
				d := x2 - x1
				ans += cnt2[y1] * cnt1[y1+d] * cnt2[y1+d]
				ans += cnt2[y1] * cnt1[y1-d] * cnt2[y1-d]
			}
		}
	}
	return
}

/**
 * Your DetectSquares object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(point);
 * param_2 := obj.Count(point);
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Use HashMap to Store Point Frequencies	Time Complexity: O(n) for iterating potential y-alignments. Space Complexity: O(N) for tracking point counts.
Use Frequency Matrix	Time Complexity: O(n) for traversal and tally operations. Space Complexity: O(1), due to static-bound array sizing.
Hash Table	–

Complexity analysis

Approach	Time	Space	When to Use
HashMap Point Frequencies	Add: O(1), Count: O(n)	O(n)	General case with dynamic points and unknown coordinate distribution
Frequency Matrix	Add: O(1), Count: O(C)	O(C²)	When coordinate range is small and predictable

Frequently asked questions

Is Detect Squares easy or hard?

Detect Squares is classified as a Medium problem on LeetCode. The implementation is straightforward once you recognize that every square can be identified by a diagonal pair and that point frequencies allow constant-time validation of the remaining corners.

Detect Squares Python/Java solution

In Python or Java, store points in a hash map where the key represents the coordinate pair and the value is the count of occurrences. The add method increments the frequency, while the count method iterates through stored points and multiplies the frequencies of the required square corners.

How to solve Detect Squares in O(n)?

Store every inserted point in a hash map with its frequency. For a query point (x, y), iterate through all points and treat (px, py) as a diagonal if |x − px| equals |y − py|. If valid, check the other two corners (x, py) and (px, y) in the map and multiply their frequencies. This gives an O(n) count operation.

What is the best approach for Detect Squares?

The most practical solution uses a HashMap to store the frequency of each point. During a count query, iterate through stored points and treat each as a potential diagonal of a square. The other two required corners are checked with constant-time hash lookups. This results in O(1) add operations and O(n) time for each count query.

Is Detect Squares asked at Google/Amazon/Meta?

Detect Squares is a common design-style geometry problem similar to questions asked at companies like Amazon and Meta. It tests the ability to combine hash tables with coordinate geometry and efficient counting logic in a custom data structure.

What data structure is used in Detect Squares?

A hash table is the primary data structure used in the optimal solution. It stores frequencies of points keyed by their coordinates, enabling constant-time lookups when verifying the other two corners of a potential square.

What is the time complexity of Detect Squares?

Using the HashMap frequency approach, the add operation runs in O(1) time and the count operation runs in O(n), where n is the number of stored points. Space complexity is O(n) because each unique coordinate pair is stored in the map.

Detect Squares solution and explanation

The problem

Approach overview

Approach 1: Use HashMap to Store Point Frequencies

Approach 2: Use Frequency Matrix

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Detect Squares solution and explanation

The problem

Approach overview

Approach 1: Use HashMap to Store Point Frequencies

Approach 2: Use Frequency Matrix

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems