Detect Squares - Solution & Explanation

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.

MediumArray Hash Table Design Counting20 min readAsked at: Amazon, Meta, Google +1

Practice this problem

Problem Statement

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.

This C solution uses a 2D array to keep track of counts of points at each coordinate. The add function increases the count for a given point, and the count function computes possible squares by checking potential vertices on vertical and horizontal alignments.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n) for counting, where n is the width of the plane (1000 in this case).
Space Complexity: O(max_coords^2) due to the array size.

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.

The implementation in C leverages a 2D array for fast access and storage, allowing for quick checks across potential square formations by the index access method. It avoids additional complexities of hash maps but presumes small constraint limits.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n) via direct index checks for valid squares.
Space Complexity: O(MAX_COORD^2), fixed by coordinate bounds.

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.

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Use HashMap to Store Point Frequencies	Time Complexity: O(n) for counting, where n is the width of the plane (1000 in this case). Space Complexity: O(max_coords^2) due to the array size.
Use Frequency Matrix	Time Complexity: O(n) via direct index checks for valid squares. Space Complexity: O(MAX_COORD^2), fixed by coordinate bounds.
Hash Table	—

Detailed 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

Video Solution

Detect Squares - Leetcode Weekly Contest - Problem 2013 - Python • NeetCode • 54,716 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Detect Squares with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance53.0%

Approaches3

Reading time20 min

Asked at

Amazon Meta Google Pure Storage

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Use HashMap to Store Point Frequencies

Code

Complexity

Approach 2: Use Frequency Matrix

Code

Complexity

Approach 3: Hash Table

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents