How to Solve Detect Squares

Start by maintaining a frequency map of all added points for constant-time access. When counting squares for a query point, scan points sharing the same x or y coordinate and use hash lookups to check potential square completions. This approach balances quick add operations with optimized count queries, avoiding unnecessary iterations over unrelated points and ensuring duplicates are correctly handled.

Problem Statement

You are given a stream of points on the X-Y plane. Implement a data structure that supports adding points and counting how many axis-aligned squares can be formed with a given query point. An axis-aligned square has edges parallel or perpendicular to the x-axis and y-axis, and all edges must have equal length.

Design a DetectSquares class with two methods: add(point) to store a new point, allowing duplicates, and count(point) to return the number of squares that can be formed using the given point as one vertex. Points coordinates range from 0 to 1000, and the total number of add and count calls does not exceed 3000.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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.

Solution Approach

Use a Hash Map to Track Point Frequencies

Maintain a nested hash map where the first key is the x-coordinate and the second key is the y-coordinate. Store the frequency of each point to quickly handle duplicate points and enable constant-time checks during counting.

Scan Along Shared Coordinates

For a count query, iterate over all points that share the same x or y coordinate with the query point. For each candidate, compute the side length and determine the positions of the other two vertices, then use the hash map to verify if they exist.

Sum Square Counts Efficiently

Multiply the frequencies of the points at the other two vertices when valid. Accumulate these products to get the total number of squares. This approach ensures duplicate points contribute correctly without redundant recalculations.

Complexity Analysis

Adding a point is O(1) because it updates the hash map. Counting squares requires scanning points along the same x or y coordinate and performing O(1) hash lookups for potential vertices, so worst-case time is O(n) where n is the number of points sharing coordinates. Space is O(p) where p is the number of distinct points stored.

What Interviewers Usually Probe

• Asks about handling duplicate points and counting their contribution to squares.
• Probes understanding of hash map use for constant-time lookup in geometric problems.
• Checks if candidate points are scanned efficiently along shared coordinates rather than all points.

Common Pitfalls or Variants

Common pitfalls

• Failing to account for duplicate points when counting squares, leading to undercounting.
• Iterating over all stored points instead of only those sharing x or y coordinates, causing slow queries.
• Incorrectly calculating positions of the other two square vertices, missing valid squares.

Follow-up variants

• Count rectangles instead of squares using similar hash map frequency logic.
• Handle dynamic deletion of points while still efficiently counting squares.
• Extend to 3D to count axis-aligned cubes using a three-level nested hash map.

How GhostInterview Helps

• Automatically tracks point frequencies and guides which coordinates to scan for valid squares.
• Identifies when candidate vertices exist and multiplies counts for duplicates to compute totals.
• Highlights inefficient full scans and suggests optimized coordinate-based hash lookups.

Topic Pages

• Array
• Hash Table
• Design
• Counting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the key pattern used in Detect Squares?

The problem relies on array scanning along shared coordinates combined with hash lookups to verify the existence of potential square vertices.

Can duplicate points affect the square count?

Yes, duplicates increase the number of valid squares. Each duplicate point is counted according to its frequency in the hash map.

What are the time complexity trade-offs?

Adding a point is O(1), but counting squares depends on the number of points sharing coordinates with the query point, potentially O(n) in worst cases.

Why use a hash map instead of an array for counts?

A hash map enables constant-time lookup for any point and handles duplicates efficiently without scanning all points.

How does GhostInterview improve solving Detect Squares?

It guides tracking point frequencies, optimizes candidate scanning, and correctly handles duplicates, ensuring accurate and fast square counts.