Detect Squares - Practice Coding Problems

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

Input & Output

Example 1 — Basic Square Formation

$ Input: operations = ["DetectSquares", "add", "add", "add", "count", "count", "add", "count"], points = [[], [3,10], [11,2], [3,2], [11,10], [14,8], [11,2], [11,10]]

› Output: [null, null, null, null, 1, 0, null, 1]

💡 Note: 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: [3, 10], [11, 2], [3, 2] detectSquares.count([14, 8]); // return 0. No valid square. detectSquares.add([11, 2]); // duplicate point detectSquares.count([11, 10]); // return 1 (still same square)

Example 2 — No Valid Squares

$ Input: operations = ["DetectSquares", "add", "add", "count"], points = [[], [0, 0], [1, 2], [0, 0]]

› Output: [null, null, null, 0]

💡 Note: Points (0,0), (1,2), and query (0,0) cannot form any square with positive area, so count returns 0.

Example 3 — Multiple Squares with Duplicates

$ Input: operations = ["DetectSquares", "add", "add", "add", "add", "count"], points = [[], [0, 0], [0, 1], [1, 0], [0, 0], [1, 1]]

› Output: [null, null, null, null, null, 2]

💡 Note: Query point (1,1) can form a square with points (0,0), (0,1), (1,0). Since (0,0) appears twice, there are 2 ways to form this square.

Constraints

At most 3000 calls in total will be made to add and count.
0 <= point[0], point[1] <= 1000

Visualization

Tap to expand

Understanding the Visualization

Input Stream

Points are added: (3,10), (11,2), (3,2)

Query Processing

Check if query point (11,10) can form squares

Square Detection

Found 1 valid square using the 3 stored points

Key Takeaway

🎯 Key Insight: For any two diagonal points of a square, the other two corners are mathematically determined by the side length

Asked in

G Google 23 a Amazon 18 M Microsoft 15 🍎 Apple 12

The key insight is that for any query point, we can iterate through all stored points as potential diagonal corners of a square. For each valid diagonal pair, the other two corners are mathematically determined. Best approach uses hash map with frequency counting for O(n) time per query and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Combinations	O(n³)	O(n)	For each query, check all possible combinations of 3 points to see if they form a square
Hash Map with Coordinate Counting	O(n)	O(n)	Use hash map to count point frequencies and iterate through potential diagonal pairs

Brute Force - Check All Combinations — Algorithm Steps

Store all added points in a list
For count queries, generate all combinations of 3 points
Check if each combination forms a square with the query point

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Points

Add each point to a list as it comes

Generate Combinations

For count query, try all combinations of 3 stored points

Validate Square

Check if 4 points form an axis-aligned square

Code -

solution.c — C

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

#define MAX_POINTS 1000

typedef struct {
    int points[MAX_POINTS][2];
    int count;
} DetectSquares;

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

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

int isSquare(int points[4][2]) {
    int xs[4], ys[4];
    for (int i = 0; i < 4; i++) {
        xs[i] = points[i][0];
        ys[i] = points[i][1];
    }
    
    // Sort coordinates
    for (int i = 0; i < 3; i++) {
        for (int j = i + 1; j < 4; j++) {
            if (xs[i] > xs[j]) {
                int temp = xs[i]; xs[i] = xs[j]; xs[j] = temp;
            }
            if (ys[i] > ys[j]) {
                int temp = ys[i]; ys[i] = ys[j]; ys[j] = temp;
            }
        }
    }
    
    // Check if we have exactly 2 unique x and 2 unique y coordinates
    if (xs[0] != xs[1] && xs[1] == xs[2] && xs[2] != xs[3] && xs[0] == xs[3]) return 0;
    if (ys[0] != ys[1] && ys[1] == ys[2] && ys[2] != ys[3] && ys[0] == ys[3]) return 0;
    
    return 1; // Simplified check
}

int detectSquaresCount(DetectSquares* obj, int* point) {
    int result = 0;
    int n = obj->count;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                int allPoints[4][2] = {
                    {point[0], point[1]},
                    {obj->points[i][0], obj->points[i][1]},
                    {obj->points[j][0], obj->points[j][1]},
                    {obj->points[k][0], obj->points[k][1]}
                };
                if (isSquare(allPoints)) {
                    result++;
                }
            }
        }
    }
    
    return result;
}

int main() {
    printf("[0,1,1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each count query, we check all combinations of 3 points from n stored points

⚠ Quadratic Growth

Space Complexity

O(n)

Store all points in a list

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler