Detect Squares

Problem in Plain English

You must support adding points from a stream, where duplicates count as distinct points, and answering how many axis-aligned squares use a given query point as one corner. Return the count for each query, weighing every choice of stored duplicates separately.

Problem Statement

Implement a point-stream data structure with an initially empty DetectSquares instance. add(point) stores one occurrence of [x,y]; repeated coordinates are distinct selectable occurrences. count(point) returns how many unordered triples of stored occurrences form a positive-area axis-aligned square together with that supplied query corner.

All four corners must be at distinct coordinates, both horizontal and vertical side lengths must match, and edges must be parallel to the coordinate axes. The query need not have been added. Stored copies of the query coordinate do not multiply the answer: the supplied query is one fixed corner. Adding stores an owned coordinate copy or immutable key, so callers can reuse their point array; counting preserves the query and the stored state.

Constraints

Each add or count point contains exactly two integers [x,y].
Both coordinates are between 0 and 1000 inclusive.
At most 3000 calls to add and count combined are made on an instance.

Examples

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]

After adding [3,10], [11,2] and [3,2], count([11,10]) finds one square with side 8. count([14,8]) finds none. Adding a duplicate [11,2] raises count([11,10]) to 2.

Example 2

Input: ["DetectSquares","count","add","add","add","count"] [[],[[0,0]],[[1,0]],[[0,1]],[[1,1]],[[0,0]]]
Output: [null,0,null,null,null,1]

Counting in an empty structure returns zero. Three later additions form a unit square with query [0,0], even though that query coordinate was never stored.

Example 3

Input: ["DetectSquares","add","add","add","add","add","add","add","count"] [[],[[1,0]],[[1,0]],[[0,1]],[[0,1]],[[0,1]],[[1,1]],[[0,0]],[[0,0]]]
Output: [null,null,null,null,null,null,null,null,6]

With fixed query [0,0], there are 2 choices for [1,0], 3 for [0,1], and 1 for [1,1], making 6 triples. The stored [0,0] is not one of the other three corners and does not multiply the answer.

Example 4

Input: ["DetectSquares","add","add","add","count"] [[],[[2,0]],[[0,1]],[[2,1]],[[0,0]]]
Output: [null,null,null,null,0]

These corners form a rectangle of width 2 and height 1, so they do not qualify as a square despite all four coordinates being distinct.

Example 5

Input: ["DetectSquares","add","add","add","count","count"] [[],[[0,1000]],[[1000,0]],[[1000,1000]],[[0,0]],[[0,0]]]
Output: [null,null,null,null,1,1]

The coordinate bounds allow a square of side 1000. Repeated counts return the same value because count does not add its query or consume stored occurrences.

Intuition

Once the query corner and its opposite corner are fixed, an axis-aligned square has no freedom left: the other corners combine their x and y coordinates. In Example 1 the query [11,10] and diagonal [3,2] force [3,10] and [11,2], with side length 8. Adding another [11,2] creates another choice for that one stored corner, doubling the count without changing the square geometry. The query is supplied once and is not drawn from stored duplicates.

Approaches

Triple Loop Check

Solution Details

Reveal Triple Loop Check: intuition, complexity, and code

Intuition

Keep every added occurrence separately and choose every triple of distinct stored indices exactly once. Check whether those three coordinates plus the supplied query are the four distinct corners of a square. Duplicate occurrences remain separate choices, making this a direct but cubic reference solution.

Step-by-Step Logic

Store an independent two-coordinate copy on each add, preserving duplicate occurrences as different indices. Example 1 assigns A=[3,10] at index 0, B=[11,2] at index 1, and C=[3,2] at index 2.
On count, reset the result and enumerate increasing triples i < j < k. With three stored points there is one triple; after the duplicate add D=[11,2] at index 3 there are four triples.
For each triple, combine its coordinates with the query and reject unless all four coordinates are distinct, with exactly two different x values and two different y values. Example 1 at query [11,10] passes these tests for ABC.
Compare the positive horizontal and vertical differences. Equal differences count one square; Example 1 gives width 8 and height 8, so the first count returns 1.
Continue all triples and return the total without changing stored points. The query [14,8] returns 0. After D is added, ABC and ACD pass while ABD and BCD repeat a coordinate, so the final count returns 2.

Why It Works

Every valid selection of three stored occurrences has exactly one increasing index order i < j < k, so the loops examine it once without permutations. Four distinct coordinates with exactly two x values and two y values must fill the entire two-by-two coordinate grid. Equal differences between those x values and those y values therefore make an axis-aligned square; distinct coordinates ensure positive side lengths. Conversely, every positive-area axis-aligned square satisfies these tests. Thus every accepted triple is valid and every valid triple is counted exactly once, including choices among duplicated occurrences. Copies of the query coordinate fail the distinct-corner test rather than multiplying results.

Dry Run

Triple Loop Check: variable states at each step
Operation / triple	Stored state or distinct-corner check	x values / y values	Side test	Running result / output
construct	empty	-	-	null
add A=[3,10]	[A]	-	-	null
add B=[11,2]	[A,B]	-	-	null
add C=[3,2]	[A,B,C]	-	-	null
count [11,10], ABC (0,1,2)	four distinct coordinates	{3,11} / {2,10}	8 equals 8	0 → 1; return 1
count [14,8], ABC (0,1,2)	four distinct coordinates	{3,11,14} / {2,8,10}	reject: three x and y values	0 → 0; return 0
add D=[11,2]	[A,B,C,D], B and D are distinct occurrences	-	-	null
count [11,10], ABC (0,1,2)	four distinct coordinates	{3,11} / {2,10}	8 equals 8	0 → 1
same count, ABD (0,1,3)	only three distinct coordinates: B=D	not evaluated	reject duplicate corner	1 → 1
same count, ACD (0,2,3)	four distinct coordinates	{3,11} / {2,10}	8 equals 8	1 → 2
same count, BCD (1,2,3)	only three distinct coordinates: B=D	not evaluated	reject duplicate corner	2 → 2; return 2
full stream output	no state changed by counts	-	-	[null,null,null,null,1,0,null,2]

Complexity Analysis

Time Complexity

O(n^3)

Space Complexity

O(n)

Let n be the number of additions so far, counting duplicates. Each count examines n(n-1)(n-2)/6 increasing-index triples, doing constant work for four points. It uses O(1) peak temporary space beyond the persistent O(n) owned point list, although it allocates constant-size sets/arrays for every candidate. add takes amortized O(1) time and stores a two-coordinate copy; construction takes O(1), and count returns one scalar. At most 2999 additions can precede a count within 3000 total calls. Exclude occurrences at the query coordinate, then form disjoint groups: horizontal candidates with the same query y and different x, vertical candidates with the same query x and different y, and off-axis candidates differing on both axes. Their sizes a,b,c sum to at most 2999. Every square uses one occurrence from each group, so count is at most abc, maximized at 999×1000×1000 = 999000000. This fits Java int and exact JavaScript integers.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3import java.util.HashSet;4import java.util.Set;5
6class DetectSquares {7    private List<int[]> pts = new ArrayList<>();8
9    public DetectSquares() {10    }11
12    public void add(int[] point) {13        // Own the coordinates: later edits to the caller’s array must not change state.14        pts.add(new int[]{point[0], point[1]});15    }16
17    public int count(int[] point) {18        int res = 0;19        int n = pts.size();20        // Increasing indices count each selection once, without permutations.21        for (int i = 0; i < n; i++) {22            for (int j = i + 1; j < n; j++) {23                for (int k = j + 1; k < n; k++) {24                    int[][] four = {point, pts.get(i), pts.get(j), pts.get(k)};25                    Set<String> seen = new HashSet<>();26                    Set<Integer> xs = new HashSet<>();27                    Set<Integer> ys = new HashSet<>();28                    for (int[] p : four) {29                        seen.add(p[0] + "," + p[1]);30                        xs.add(p[0]);31                        ys.add(p[1]);32                    }33                    // Four distinct corners must fill a 2-by-2 grid before side checks.34                    if (seen.size() == 4 && xs.size() == 2 && ys.size() == 2) {35                        int[] xa = new int[2];36                        int t = 0;37                        for (int x : xs) xa[t++] = x;38                        int[] ya = new int[2];39                        t = 0;40                        for (int y : ys) ya[t++] = y;41                        int dx = Math.abs(xa[0] - xa[1]);42                        int dy = Math.abs(ya[0] - ya[1]);43                        if (dx == dy) res++;44                    }45                }46            }47        }48        return res;49    }50}

Hints

Hint 1

A square is fixed once you know two opposite corners.

Hint 2

For a fixed query point, each stored point is a candidate for the opposite corner, and the other two corners are then forced.

Hint 3

Counting duplicates with a frequency map and multiplying the corner counts handles repeated points without extra loops.

Edge Cases

An empty structure or fewer than three stored occurrences always returns 0.
The query does not need to be present; stored duplicates at the query coordinate do not multiply answers.
Duplicate diagonal and adjacent corners multiply independently: counts 2,3,4 give 24 triples.
Same-row/column candidates and repeated coordinates cannot form positive-area squares.
Rectangles with unequal side lengths and rotated squares are rejected: only equal-sided, axis-aligned grids count.
Diagonals can lie in all four quadrants relative to the query; compare absolute differences.
Coordinates 0 and 1000 can be opposite edges of a side-1000 square.
Mutating a point array after add must not change stored coordinates; repeated count calls must not modify the structure.

Common Mistakes and Interview Tips

Replacing frequencies with a set loses distinct duplicate choices.
Scanning duplicate occurrences and also multiplying by the diagonal frequency double-counts that corner. Scan distinct keys once.
Multiplying by the stored query frequency is wrong: the supplied query is one fixed corner and may not be stored at all.
Counting all permutations of a stored triple overcounts by six; the reference approach uses increasing indices.
Using equal signed differences misses diagonals in two quadrants. Use absolute differences and reject a zero difference.
Accepting merely two x values and two y values without four distinct coordinates can admit missing or repeated corners.
Retaining the caller’s mutable point array makes later edits corrupt the stored stream. Copy its values or build an immutable key.
A count lookup should use a noninserting read; adding missing keys while iterating mutates state and may invalidate iteration.
Interview tip: give method-specific complexities and distinguish n additions from u unique coordinates; duplicates change counts without necessarily increasing scan cost.

Key Takeaway

For a fixed geometric query, find a unique structural witness such as the opposite corner. It forces remaining coordinates, allowing frequency lookups and a product of independent duplicate choices instead of enumerating every tuple.