LeetCode 2013 - Detect Squares

The problem presents a stream of points in a 2D plane and asks us to design a data structure that supports two operations efficiently: adding points and counting squares.

leetcodemediumarrayhash-tabledesigncountingdata-stream

LeetCode Problem 2013

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Design, Counting, Data Stream

Solution

Problem Understanding

The problem presents a stream of points in a 2D plane and asks us to design a data structure that supports two operations efficiently: adding points and counting squares. The add operation inserts a point into the data structure, and the count operation calculates the number of axis-aligned squares that can be formed using the query point and any three points already stored. An axis-aligned square is defined as a square whose sides are parallel or perpendicular to the x-axis and y-axis, meaning the coordinates of its vertices follow a strict pattern along the axes.

The input consists of integer points [x, y] where 0 <= x, y <= 1000. Duplicate points are allowed, which means we may have multiple instances of the same coordinate, and each instance counts separately when forming squares. The output is an integer representing the number of distinct ways to form an axis-aligned square using the query point and three previously added points.

The constraints-at most 3000 calls to add and count-suggest that a naive brute-force solution that iterates through all possible triplets of points for each count operation would likely be too slow. Edge cases include queries on points that have no potential square partners, duplicate points, and squares with sides of length zero (which are invalid as the area must be positive).

Approaches

Brute Force Approach

The brute-force approach involves storing all added points in a list. For a count query, we would iterate over all combinations of three points from the stored list and check if they form a square with the query point. To validate a square, we would calculate all pairwise distances and ensure that there are two equal distances for sides and one longer distance for the diagonal. This approach works in principle but has a time complexity of O(n^3) per query where n is the number of points, which is unacceptable for 3000 operations because it could lead to over 27 billion iterations in the worst case.

Optimal Approach

The key insight is that we are only counting axis-aligned squares, meaning the sides are strictly horizontal or vertical. This allows us to exploit hash maps to store the frequency of points for efficient lookup. For a query point (x, y), an axis-aligned square's other three vertices must lie on the same x or y coordinates:

  1. The square has sides parallel to the axes, so if one vertex is (x, y), the opposite vertex must be (x + side_length, y + side_length) or similar variations.
  2. By iterating only through points that share the same x or y coordinate with the query point, we reduce the search space drastically.
  3. We maintain a map of maps where the outer map is keyed by x-coordinate and the inner map counts occurrences of y-coordinates, enabling O(1) lookup for points at specific positions.

This reduces the count query to O(n) where n is the number of points along the same x-coordinate as the query, and adding a point is O(1).

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) per query O(n) Iterates all triplets to check squares, too slow
Optimal O(n) per query, O(1) per add O(n) Uses hashmap to count points, leverages axis alignment for efficiency

Algorithm Walkthrough

  1. Initialize Data Structure: Create a dictionary points_count where each key is an x-coordinate, and the value is another dictionary mapping y-coordinates to their counts.
  2. Add Operation: When adding a point (x, y), increment points_count[x][y] by 1. If x or y does not exist in the maps, initialize them.
  3. Count Operation: For a query point (x, y):
  • Initialize a variable total_squares = 0.
  • Iterate over all x-coordinates col_x in points_count where col_x != x.
  • For each candidate x-coordinate, calculate the potential square's side length side = col_x - x.
  • Check the two possible y-coordinates (y + side) and (y - side) for forming a square.
  • For each candidate vertex, multiply the counts of the three other points that would form a square with (x, y) and add to total_squares.
  1. Return Result: After iterating all candidates, return total_squares.

Why it works: The algorithm leverages the properties of axis-aligned squares. By iterating only through points on different x-coordinates and checking the corresponding y-coordinates, we ensure that all squares are considered exactly once, accounting for duplicate points through the stored counts.

Python Solution

from collections import defaultdict
from typing import List

class DetectSquares:

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

    def add(self, point: List[int]) -> None:
        x, y = point
        self.points_count[x][y] += 1

    def count(self, point: List[int]) -> int:
        x, y = point
        total_squares = 0
        if x not in self.points_count:
            return 0
        for col_x, y_map in self.points_count.items():
            if col_x == x:
                continue
            side_length = col_x - x
            # Check for squares above and below the query point
            for delta_y in [side_length, -side_length]:
                y2 = y + delta_y
                if y2 in y_map:
                    count1 = self.points_count[x].get(y, 0)
                    count2 = y_map[y]
                    count3 = y_map[y2]
                    total_squares += count1 * count2 * count3
        return total_squares

Explanation: The add function updates the count of each point in a nested dictionary. The count function iterates over possible x-coordinates for the other vertices, computes side lengths, and checks the presence of corresponding y-coordinates to ensure an axis-aligned square. Multiplying the counts handles duplicate points correctly.

Go Solution

type DetectSquares struct {
	pointsCount map[int]map[int]int
}

func Constructor() DetectSquares {
	return DetectSquares{pointsCount: make(map[int]map[int]int)}
}

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

func (this *DetectSquares) Count(point []int) int {
	x, y := point[0], point[1]
	total := 0
	for colX, yMap := range this.pointsCount {
		if colX == x {
			continue
		}
		side := colX - x
		for _, deltaY := range []int{side, -side} {
			y2 := y + deltaY
			if count, ok := yMap[y2]; ok {
				total += this.pointsCount[x][y] * yMap[y] * count
			}
		}
	}
	return total
}

Go-specific Notes: The nested maps mimic Python's defaultdict. Nil checks ensure safe map operations. Multiplication of counts handles duplicates.

Worked Examples

Example Input Sequence:

["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
Step Operation points_count state count result
1 add([3,10]) {3: {10: 1}} -
2 add([11,2]) {3:{10:1},11:{2:1}} -
3 add([3,2]) {3:{10:1,2:1},11:{2:1}} -
4 count([11,10]) same 1
5 count([14,8]) same 0
6 add([11,2]) {3:{10:1,2:1},11:{2:2}} -
7 count([11,10]) same 2

Complexity Analysis

Measure Complexity Explanation
Time (add) O(1) Insertion in hashmap is constant time
Time (count) O(n) Iterate over all x-coordinates in the map
Space O(n) Store counts of all added points

The time complexity for count is efficient because it does not require checking all combinations of three points; it only examines relevant candidates along aligned axes.

Test Cases

obj = DetectSquares()
obj.add([3, 10])
obj.add([11, 2])
obj.add([3, 2])
assert obj.count([11, 10]) == 1  # basic square test
assert obj.count([14, 8]) == 0   # no squares
obj.add([11, 2])