2013. Detect Squares - Explanation

Description

You are given a stream of points consisting of x-y coordinates on a 2-D plane. Points can be added and queried as follows:

Add - new points can be added to the stream into a data structure. Duplicate points are allowed and should be treated as separate points.
Query - Given a single query point, count the number of ways to choose three additional points from the data structure such that the three points and the query point form a square. The square must have all sides parallel to the x-axis and y-axis, i.e. no diagonal squares are allowed. Recall that a square must have four equal sides.

Implement the CountSquares class:

CountSquares() Initializes the object.
void add(int[] point) Adds a new point point = [x, y].
int count(int[] point) Counts the number of ways to form valid squares with point point = [x, y] as described above.

Example 1:

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

Explanation:
CountSquares countSquares = new CountSquares();
countSquares.add([1, 1]);
countSquares.add([2, 2]);
countSquares.add([1, 2]);

countSquares.count([2, 1]);   // return 1.
countSquares.count([3, 3]);   // return 0.
countSquares.add([2, 2]);     // Duplicate points are allowed.
countSquares.count([2, 1]);   // return 2.

Constraints:

point.length == 2
0 <= x, y <= 1000

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(1) time for each add() call, O(n) time for each count() call, and O(n) space, where n is the total number of points.

Hint 1

Initially, we can store the points in a global list for the add() call. For the count() call, a brute force approach would use three nested loops to check other points except for the query point, resulting in an O(n^3) time solution. Can you think of a better way? Maybe you should consider the observation that can be drawn from the diagonal of a square.

Hint 2

In a square's diagonal, the absolute difference between the x-coordinates is equal to the absolute difference between the y-coordinates of the two endpoints, and neither difference can be zero. Using these two points, we can determine the other diagonal endpoints.

Hint 3

We store points in a hash map instead of a list for O(1) lookups, treating duplicate points as one while tracking their frequencies. For the count() function, we iterate through points that, along with the query point, can form a diagonal. Let the query point be (qx, qy) and the other point be (x, y), ensuring they form a diagonal. What could be the other two points? Maybe you should consider the points forming a right-to-left diagonal, treating (qx, qy) as the top-right corner.

Hint 4

The other two points are point1 (x, qy) and point2 (qx, y). For counting, we simply add count of point1 * count of point2 to the result res.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Maps - Using dictionaries to store and retrieve point counts in O(1) time
Coordinate Geometry - Understanding axis-aligned squares and diagonal relationships between corners
Nested Hash Maps - Using two-level hash maps to efficiently query points by x-coordinate then y-coordinate

1. Hash Map - I

Intuition

We are asked to count how many axis-aligned squares can be formed using a given point as one corner and previously added points as the other three corners.

Key observations about an axis-aligned square:

All sides are parallel to the x-axis and y-axis
If (px, py) is one corner and (x, y) is the diagonal opposite corner, then:
- |px - x| == |py - y| (equal side lengths)
- x != px and y != py (otherwise it would not form a square)
The other two required corners must be:
- (x, py)
- (px, y)

So the idea is:

Fix the query point (px, py)
Try every previously added point (x, y) as a possible diagonal
If it forms a valid square diagonal, multiply how many times the other two required points exist

A hash map lets us quickly check how many times a specific point was added.

Algorithm

Data Structures

ptsCount: a hash map storing how many times each point appears
pts: a list of all added points (including duplicates)

add(point)

Increment the count of point in ptsCount
Append point to the list pts

count(point)

Initialize res = 0
Let (px, py) be the query point
For every stored point (x, y) in pts:
- Check if (x, y) can be the diagonal opposite corner:
  - |px - x| == |py - y|
  - x != px and y != py
- If not valid, skip
If valid:
- The other two corners must be (x, py) and (px, y)
- Add to the result:
  - ptsCount[(x, py)] * ptsCount[(px, y)]
Return res

class CountSquares:
    def __init__(self):
        self.ptsCount = defaultdict(int)
        self.pts = []

    def add(self, point: List[int]) -> None:
        self.ptsCount[tuple(point)] += 1
        self.pts.append(point)

    def count(self, point: List[int]) -> int:
        res = 0
        px, py = point
        for x, y in self.pts:
            if (abs(py - y) != abs(px - x)) or x == px or y == py:
                continue
            res += self.ptsCount[(x, py)] * self.ptsCount[(px, y)]
        return res

public class CountSquares {
    private Map<List<Integer>, Integer> ptsCount;
    private List<List<Integer>> pts;

    public CountSquares() {
        ptsCount = new HashMap<>();
        pts = new ArrayList<>();
    }

    public void add(int[] point) {
        List<Integer> p = Arrays.asList(point[0], point[1]);
        ptsCount.put(p, ptsCount.getOrDefault(p, 0) + 1);
        pts.add(p);
    }

    public int count(int[] point) {
        int res = 0;
        int px = point[0], py = point[1];
        for (List<Integer> pt : pts) {
            int x = pt.get(0), y = pt.get(1);
            if (Math.abs(py - y) != Math.abs(px - x) || x == px || y == py) {
                continue;
            }
            res += ptsCount.getOrDefault(Arrays.asList(x, py), 0) *
                   ptsCount.getOrDefault(Arrays.asList(px, y), 0);
        }
        return res;
    }
}

class CountSquares {
private:
    unordered_map<long, int> ptsCount;
    vector<vector<int>> pts;

    long getKey(int x, int y) {
        return (static_cast<long>(x) << 32) | static_cast<long>(y);
    }

public:
    CountSquares() {
    }

    void add(vector<int> point) {
        long key = getKey(point[0], point[1]);
        ptsCount[key]++;
        pts.push_back(point);
    }

    int count(vector<int> point) {
        int res = 0;
        int px = point[0], py = point[1];

        for (const auto& pt : pts) {
            int x = pt[0], y = pt[1];
            if (abs(py - y) != abs(px - x) || x == px || y == py) continue;
            res += ptsCount[getKey(x, py)] * ptsCount[getKey(px, y)];
        }
        return res;
    }
};

class CountSquares {
    constructor() {
        this.ptsCount = new Map();
        this.pts = [];
    }

    /**
     * @param {number[]} point
     * @return {void}
     */
    add(point) {
        const p = point.join(',');
        this.ptsCount.set(p, (this.ptsCount.get(p) || 0) + 1);
        this.pts.push(point);
    }

    /**
     * @param {number[]} point
     * @return {number}
     */
    count(point) {
        let res = 0;
        const [px, py] = point;
        for (const [x, y] of this.pts) {
            if (Math.abs(py - y) !== Math.abs(px - x) || x === px || y === py) {
                continue;
            }
            res +=
                (this.ptsCount.get(`${x},${py}`) || 0) *
                (this.ptsCount.get(`${px},${y}`) || 0);
        }
        return res;
    }
}

public class CountSquares {
    private Dictionary<(int, int), int> ptsCount;
    private List<int[]> pts;

    public CountSquares() {
        ptsCount = new Dictionary<(int, int), int>();
        pts = new List<int[]>();
    }

    public void Add(int[] point) {
        var tuplePoint = (point[0], point[1]);
        if (!ptsCount.ContainsKey(tuplePoint))
            ptsCount[tuplePoint] = 0;

        ptsCount[tuplePoint]++;
        pts.Add(point);
    }

    public int Count(int[] point) {
        int res = 0;
        int px = point[0];
        int py = point[1];

        foreach (var pt in pts) {
            int x = pt[0];
            int y = pt[1];

            if (Math.Abs(py - y) != Math.Abs(px - x) || x == px || y == py)
                continue;

            res += (ptsCount.GetValueOrDefault((x, py)) *
                   ptsCount.GetValueOrDefault((px, y)));
        }
        return res;
    }
}

type CountSquares struct {
    ptsCount map[Point]int
    pts      []Point
}

type Point struct {
    x, y int
}

func Constructor() CountSquares {
    return CountSquares{
        ptsCount: make(map[Point]int),
        pts:      make([]Point, 0),
    }
}

func (this *CountSquares) Add(point []int) {
    p := Point{point[0], point[1]}
    this.ptsCount[p]++
    this.pts = append(this.pts, p)
}

func (this *CountSquares) Count(point []int) int {
    res := 0
    px, py := point[0], point[1]

    for _, pt := range this.pts {
        if abs(py-pt.y) != abs(px-pt.x) || pt.x == px || pt.y == py {
            continue
        }

        p1 := Point{pt.x, py}
        p2 := Point{px, pt.y}

        res += this.ptsCount[p1] * this.ptsCount[p2]
    }

    return res
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

class CountSquares() {
    private val pointCounts = HashMap<Pair<Int, Int>, Int>()
    private val points = mutableListOf<IntArray>()

    fun add(point: IntArray) {
        val pair = Pair(point[0], point[1])
        pointCounts[pair] = pointCounts.getOrDefault(pair, 0) + 1
        points.add(point)
    }

    fun count(point: IntArray): Int {
        var result = 0
        val (px, py) = point

        for ((x, y) in points) {
            if (kotlin.math.abs(py - y) != kotlin.math.abs(px - x) ||
                x == px || y == py) {
                continue
            }
            result += (pointCounts[Pair(x, py)] ?: 0) * (pointCounts[Pair(px, y)] ?: 0)
        }
        return result
    }
}

class CountSquares {
    private var ptsCount: [String: Int]
    private var pts: [[Int]]

    init() {
        self.ptsCount = [:]
        self.pts = []
    }

    func add(_ point: [Int]) {
        let key = "\(point[0]),\(point[1])"
        ptsCount[key, default: 0] += 1
        pts.append(point)
    }

    func count(_ point: [Int]) -> Int {
        var res = 0
        let px = point[0], py = point[1]

        for pt in pts {
            let x = pt[0], y = pt[1]
            if abs(py - y) != abs(px - x) || x == px || y == py {
                continue
            }
            let key1 = "\(x),\(py)"
            let key2 = "\(px),\(y)"
            res += (ptsCount[key1] ?? 0) * (ptsCount[key2] ?? 0)
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(1)$ for $add()$ , $O(n)$ for $count()$ .
Space complexity: $O(n)$

2. Hash Map - II

Intuition

We want to count how many axis-aligned squares can be formed using the given query point (x1, y1) as one corner.

For an axis-aligned square:

One side is vertical and one side is horizontal
If we pick another point (x1, y2) on the same vertical line (same x1), then:
- the side length is side = y2 - y1
- this determines where the square’s other x-coordinates must be:
  - x3 = x1 + side (square to the right)
  - x4 = x1 - side (square to the left)

So for each possible vertical partner (x1, y2), we can form up to two squares:

Square to the right needs points:
- (x3, y1) and (x3, y2)
Square to the left needs points:
- (x4, y1) and (x4, y2)

Because points can be added multiple times, the total number of squares is the product of the counts of the required points.

This version uses a nested hash map:

ptsCount[x][y] = how many times point (x, y) was added
which makes counting fast and avoids storing a list of all points.

Algorithm

Data Structure

ptsCount: nested hash map
- outer key: x-coordinate
- inner key: y-coordinate
- value: count of that point

add(point)

Let the point be (x, y).
Increment ptsCount[x][y].

count(point)

Initialize res = 0.
Let the query point be (x1, y1).
Iterate over all y2 such that a point (x1, y2) exists (same x-coordinate):
Compute the side length:
- side = y2 - y1
- If side == 0, skip (same point, no square)
Compute possible horizontal positions:
- x3 = x1 + side (right square)
- x4 = x1 - side (left square)
Add squares formed to the right:
- ptsCount[x1][y2] * ptsCount[x3][y1] * ptsCount[x3][y2]
Add squares formed to the left:
- ptsCount[x1][y2] * ptsCount[x4][y1] * ptsCount[x4][y2]
Return res.

class CountSquares:

    def __init__(self):
        self.ptsCount = defaultdict(lambda: defaultdict(int))

    def add(self, point: List[int]) -> None:
        self.ptsCount[point[0]][point[1]] += 1

    def count(self, point: List[int]) -> int:
        res = 0
        x1, y1 = point
        for y2 in self.ptsCount[x1]:
            side = y2 - y1
            if side == 0:
                continue

            x3, x4 = x1 + side, x1 - side
            res += (self.ptsCount[x1][y2] * self.ptsCount[x3][y1] *
                    self.ptsCount[x3][y2])

            res += (self.ptsCount[x1][y2] * self.ptsCount[x4][y1] *
                    self.ptsCount[x4][y2])
        return res

public class CountSquares {
    private Map<Integer, Map<Integer, Integer>> ptsCount;

    public CountSquares() {
        ptsCount = new HashMap<>();
    }

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

    public int count(int[] point) {
        int res = 0, x1 = point[0], y1 = point[1];

        if (!ptsCount.containsKey(x1)) return res;

        for (int y2 : ptsCount.get(x1).keySet()) {
            int side = y2 - y1;
            if (side == 0) continue;

            int x3 = x1 + side, x4 = x1 - side;
            res += ptsCount.get(x1).get(y2) *
                   ptsCount.getOrDefault(x3, new HashMap<>()).getOrDefault(y1, 0) *
                   ptsCount.getOrDefault(x3, new HashMap<>()).getOrDefault(y2, 0);

            res += ptsCount.get(x1).get(y2) *
                   ptsCount.getOrDefault(x4, new HashMap<>()).getOrDefault(y1, 0) *
                   ptsCount.getOrDefault(x4, new HashMap<>()).getOrDefault(y2, 0);
        }

        return res;
    }
}

class CountSquares {
    unordered_map<int, unordered_map<int, int>> ptsCount;

public:
    CountSquares() {}

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

    int count(vector<int> point) {
        int res = 0;
        int x1 = point[0], y1 = point[1];

        for (auto &[y2, cnt] : ptsCount[x1]) {
            int side = y2 - y1;
            if (side == 0) continue;

            int x3 = x1 + side, x4 = x1 - side;
            res += cnt * ptsCount[x3][y1] * ptsCount[x3][y2];
            res += cnt * ptsCount[x4][y1] * ptsCount[x4][y2];
        }

        return res;
    }
};

class CountSquares {
    constructor() {
        this.ptsCount = new Map();
    }

    /**
     * @param {number[]} point
     * @return {void}
     */
    add(point) {
        const [x, y] = point;
        if (!this.ptsCount.has(x)) this.ptsCount.set(x, new Map());
        const yCount = this.ptsCount.get(x);
        yCount.set(y, (yCount.get(y) || 0) + 1);
    }

    /**
     * @param {number[]} point
     * @return {number}
     */
    count(point) {
        let res = 0;
        const [x1, y1] = point;
        if (!this.ptsCount.has(x1)) return res;

        const x1Points = this.ptsCount.get(x1);
        for (const [y2, cnt] of x1Points) {
            const side = y2 - y1;
            if (side === 0) continue;

            const x3 = x1 + side;
            const x4 = x1 - side;

            res +=
                cnt *
                (this.ptsCount.get(x3)?.get(y1) || 0) *
                (this.ptsCount.get(x3)?.get(y2) || 0);

            res +=
                cnt *
                (this.ptsCount.get(x4)?.get(y1) || 0) *
                (this.ptsCount.get(x4)?.get(y2) || 0);
        }

        return res;
    }
}

public class CountSquares {
    private Dictionary<int, Dictionary<int, int>> ptsCount;

    public CountSquares() {
        ptsCount = new Dictionary<int, Dictionary<int, int>>();
    }

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

    public int Count(int[] point) {
        int res = 0;
        int x1 = point[0], y1 = point[1];

        if (!ptsCount.ContainsKey(x1)) return res;

        foreach (var kv in ptsCount[x1]) {
            int y2 = kv.Key, cnt = kv.Value;
            int side = y2 - y1;
            if (side == 0) continue;

            int x3 = x1 + side, x4 = x1 - side;

            res += cnt *
                   (ptsCount.ContainsKey(x3) &&
                    ptsCount[x3].ContainsKey(y1) ? ptsCount[x3][y1] : 0) *
                   (ptsCount.ContainsKey(x3) &&
                    ptsCount[x3].ContainsKey(y2) ? ptsCount[x3][y2] : 0);

            res += cnt *
                   (ptsCount.ContainsKey(x4) &&
                    ptsCount[x4].ContainsKey(y1) ? ptsCount[x4][y1] : 0) *
                   (ptsCount.ContainsKey(x4) &&
                    ptsCount[x4].ContainsKey(y2) ? ptsCount[x4][y2] : 0);
        }

        return res;
    }
}

type CountSquares struct {
    ptsCount map[int]map[int]int
}

func Constructor() CountSquares {
    return CountSquares{
        ptsCount: make(map[int]map[int]int),
    }
}

func (this *CountSquares) Add(point []int) {
    x, y := point[0], point[1]
    if this.ptsCount[x] == nil {
        this.ptsCount[x] = make(map[int]int)
    }
    this.ptsCount[x][y]++
}

func (this *CountSquares) Count(point []int) int {
    res := 0
    x1, y1 := point[0], point[1]

    for y2 := range this.ptsCount[x1] {
        side := y2 - y1
        if side == 0 {
            continue
        }

        x3, x4 := x1+side, x1-side

        if _, exists := this.ptsCount[x3]; exists {
            res += this.ptsCount[x1][y2] * this.ptsCount[x3][y1] * this.ptsCount[x3][y2]
        }

        if _, exists := this.ptsCount[x4]; exists {
            res += this.ptsCount[x1][y2] * this.ptsCount[x4][y1] * this.ptsCount[x4][y2]
        }
    }
    return res
}

class CountSquares {
    private val points = HashMap<Int, HashMap<Int, Int>>()

    fun add(point: IntArray) {
        val x = point[0]
        val y = point[1]

        if (!points.containsKey(x)) {
            points[x] = hashMapOf()
        }

        points[x]?.put(y, (points[x]?.get(y) ?: 0) + 1)
    }

    fun count(point: IntArray): Int {
        var result = 0
        val x1 = point[0]
        val y1 = point[1]

        points[x1]?.forEach { (y2, count1) ->
            if (y2 == y1) return@forEach

            val side = Math.abs(y2 - y1)

            val x3 = x1 + side
            if (points.containsKey(x3)) {
                val count2 = points[x3]?.get(y1) ?: 0
                val count3 = points[x3]?.get(y2) ?: 0
                result += count1 * count2 * count3
            }

            val x4 = x1 - side
            if (points.containsKey(x4)) {
                val count2 = points[x4]?.get(y1) ?: 0
                val count3 = points[x4]?.get(y2) ?: 0
                result += count1 * count2 * count3
            }
        }

        return result
    }
}

class CountSquares {
    var ptsCount: [Int: [Int: Int]]

    init() {
        ptsCount = [:]
    }

    func add(_ point: [Int]) {
        let x = point[0]
        let y = point[1]
        ptsCount[x, default: [:]][y, default: 0] += 1
    }

    func count(_ point: [Int]) -> Int {
        var res = 0
        let x1 = point[0]
        let y1 = point[1]

        if let yMap = ptsCount[x1] {
            for (y2, countXY2) in yMap {
                let side = y2 - y1
                if side == 0 { continue }
                let x3 = x1 + side
                let x4 = x1 - side
                res += countXY2 * (ptsCount[x3]?[y1] ?? 0) * (ptsCount[x3]?[y2] ?? 0)
                res += countXY2 * (ptsCount[x4]?[y1] ?? 0) * (ptsCount[x4]?[y2] ?? 0)
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(1)$ for $add()$ , $O(n)$ for $count()$ .
Space complexity: $O(n)$

Common Pitfalls

Forgetting to Check Both Diagonal Conditions

A common mistake is only checking that the side lengths are equal (|px - x| == |py - y|) without also verifying that the points are not on the same horizontal or vertical line. Both conditions are necessary for a valid square diagonal.

# Wrong: Missing the x != px and y != py checks
if abs(py - y) == abs(px - x):  # Accepts invalid diagonals
    ...

# Correct: Must also ensure points form a true diagonal
if abs(py - y) == abs(px - x) and x != px and y != py:
    ...

Not Handling Duplicate Points

The problem allows adding the same point multiple times. Using a set instead of a counter for point tracking will lose count information, causing incorrect results when the same point appears multiple times. The number of squares should multiply by the count of each required corner point.

Confusing Diagonal vs Adjacent Corners

When iterating through stored points to find potential squares, some solutions incorrectly look for adjacent corners instead of diagonal corners. Given the query point (px, py) and a candidate diagonal (x, y), the other two corners must be (x, py) and (px, y), not (px + side, py) and (px, py + side).