Minimum Skips to Arrive at Meeting On Time

Description

You are given a stream of points on a two-dimensional X-Y coordinate plane. Your task is to design a data structure that supports two operations:

Add a new point from the stream into your data structure. Duplicate points are allowed and should be treated as separate, distinct points.
Count the number of ways to choose three points from the stored data such that those three points, together with a given query point, form an axis-aligned square with positive area.

An axis-aligned square is a square whose four sides are all the same length and each side is either parallel to the x-axis or parallel to the y-axis. In other words, the square cannot be rotated — its edges must be perfectly horizontal and vertical.

You need to implement the DetectSquares class with the following methods:

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 using the query point point = [x, y] as one of the four corners and three other points chosen from the stored data.

Coordinate plane showing four points forming an axis-aligned square: (3,10), (11,10), (11,2), and (3,2)

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]

Explanation:

DetectSquares() — Initialize with empty data.
add([3, 10]) — Store point (3, 10).
add([11, 2]) — Store point (11, 2).
add([3, 2]) — Store point (3, 2).
count([11, 10]) → 1. The stored points (3, 10), (11, 2), and (3, 2) form an axis-aligned square with the query point (11, 10). The square has corners at (3, 2), (3, 10), (11, 2), (11, 10) with side length 8. There is exactly 1 way to choose these three stored points.
count([14, 8]) → 0. No combination of three stored points can form an axis-aligned square with (14, 8).
add([11, 2]) — Store another copy of point (11, 2). Now (11, 2) appears twice.
count([11, 10]) → 2. The same square exists as before, but now point (11, 2) has two copies. We can pick either copy as the third stored point, giving us 2 distinct ways.

Example 2

Input:

["DetectSquares", "add", "add", "add", "add", "count"]
[[], [[0, 0]], [[0, 2]], [[2, 0]], [[2, 2]], [[0, 0]]]

Output: [null, null, null, null, null, 1]

Explanation:

After adding (0, 0), (0, 2), (2, 0), and (2, 2), calling count([0, 0]) returns 1. The query point (0, 0) combines with stored points (0, 2), (2, 0), and (2, 2) to form a 2×2 square. Note that even though (0, 0) itself is also stored, the query point is separate — we only choose 3 points from storage, and (0, 0) in storage is not needed for this square.

Constraints

point.length == 2
0 ≤ x, y ≤ 1000
At most 3000 calls in total will be made to add and count.

Editorial

Brute Force

Intuition

Let us start with the most straightforward idea. When we receive a query point, say (x1, y1), we need to find three stored points that together with (x1, y1) form an axis-aligned square.

Think about it like this: if you pin a thumbtack at (x1, y1) on a piece of graph paper, you need to find three other thumbtacks already on the paper that complete a perfect square with horizontal and vertical sides.

Since the square must be axis-aligned, one key observation is that two corners of the square must share the same y-coordinate (they sit on the same horizontal line) and two corners must share the same x-coordinate (they sit on the same vertical line). So if (x1, y1) is one corner, there must be another point at (x2, y1) directly to its left or right — these two form a horizontal edge of the square.

Once we know the horizontal edge, the side length is |x2 - x1|, and the remaining two corners must be directly above or below at (x1, y1 ± side) and (x2, y1 ± side).

The brute force approach stores all points in a simple list. For each count query, we scan through the list to find horizontal partners (points sharing the same y-coordinate), then scan again to verify whether the remaining two corners exist. Each verification requires a full scan of the list, making this approach slow.

Step-by-Step Explanation

Let's trace through count([11, 10]) after adding points (3, 10), (11, 2), and (3, 2).

Stored points list: [(3, 10), (11, 2), (3, 2)]

Step 1: Query point is (11, 10). We scan all stored points looking for horizontal partners — points that share y = 10.

Step 2: Check stored point (3, 10). Its y-coordinate is 10, matching our query. This is a horizontal partner! The side length is |3 − 11| = 8.

Step 3: Check for an upward square (y = 10 + 8 = 18). We need points at (11, 18) and (3, 18). Scan the entire stored list — neither exists. Zero upward squares.

Step 4: Check for a downward square (y = 10 − 8 = 2). We need points at (11, 2) and (3, 2). Scan the stored list — (11, 2) is found once at index 1, and (3, 2) is found once at index 2. Count = 1 × 1 = 1 square.

Step 5: Add 1 to result. Running total = 1.

Step 6: Check stored point (11, 2). Its y = 2 ≠ 10. Not a horizontal partner — skip.

Step 7: Check stored point (3, 2). Its y = 2 ≠ 10. Not a horizontal partner — skip.

Step 8: All stored points examined. Return result = 1.

Brute Force — Scanning Stored Points for Square Corners — Watch how we iterate through stored points looking for horizontal partners, then scan the entire list again to verify the remaining two corners of each potential square.

Algorithm

Data Structure: Store all added points in a list.

add(point):

Append the point to the list.

count(point):

Let the query point be (x1, y1). Initialize result = 0.
For each stored point (x2, y2) in the list:
- If y2 == y1 and x2 ≠ x1, this is a horizontal partner.
- Compute side = |x2 − x1|.
- Scan the entire list to count occurrences of (x1, y1 + side) and (x2, y1 + side). Multiply the counts and add to result (upward square).
- Scan the entire list to count occurrences of (x1, y1 − side) and (x2, y1 − side). Multiply the counts and add to result (downward square).
Return result.

Code

#include <vector>
#include <cmath>
using namespace std;

class DetectSquares {
    vector<pair<int,int>> points;

    int countPoint(int x, int y) {
        int c = 0;
        for (auto& [px, py] : points)
            if (px == x && py == y) c++;
        return c;
    }

public:
    DetectSquares() {}

    void add(vector<int> point) {
        points.push_back({point[0], point[1]});
    }

    int count(vector<int> point) {
        int x1 = point[0], y1 = point[1];
        int result = 0;
        for (auto& [x2, y2] : points) {
            if (y2 == y1 && x2 != x1) {
                int side = abs(x2 - x1);
                result += countPoint(x1, y1 + side) * countPoint(x2, y1 + side);
                result += countPoint(x1, y1 - side) * countPoint(x2, y1 - side);
            }
        }
        return result;
    }
};

class DetectSquares:
    def __init__(self):
        self.points = []

    def add(self, point: list[int]) -> None:
        self.points.append(point)

    def count(self, point: list[int]) -> int:
        x1, y1 = point
        result = 0
        for x2, y2 in self.points:
            if y2 == y1 and x2 != x1:
                side = abs(x2 - x1)
                up_c1 = sum(1 for px, py in self.points if px == x1 and py == y1 + side)
                up_c2 = sum(1 for px, py in self.points if px == x2 and py == y1 + side)
                dn_c1 = sum(1 for px, py in self.points if px == x1 and py == y1 - side)
                dn_c2 = sum(1 for px, py in self.points if px == x2 and py == y1 - side)
                result += up_c1 * up_c2 + dn_c1 * dn_c2
        return result

import java.util.*;

class DetectSquares {
    private List<int[]> points;

    public DetectSquares() {
        points = new ArrayList<>();
    }

    public void add(int[] point) {
        points.add(point.clone());
    }

    private int countPoint(int x, int y) {
        int c = 0;
        for (int[] p : points)
            if (p[0] == x && p[1] == y) c++;
        return c;
    }

    public int count(int[] point) {
        int x1 = point[0], y1 = point[1];
        int result = 0;
        for (int[] p : points) {
            if (p[1] == y1 && p[0] != x1) {
                int side = Math.abs(p[0] - x1);
                result += countPoint(x1, y1 + side) * countPoint(p[0], y1 + side);
                result += countPoint(x1, y1 - side) * countPoint(p[0], y1 - side);
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity:

add: O(1) — simply appending to a list.
count: O(n²) where n is the number of stored points.
- The outer loop iterates through all n stored points to find horizontal partners.
- For each horizontal partner found, we perform 4 full list scans (one for each needed corner in two directions), each costing O(n).
- In the worst case, all n points share the same y-coordinate, giving n partners × O(n) scanning = O(n²).

Space Complexity: O(n)

We store all n points in a list. No additional data structures are used.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time per count query because for every horizontal partner, we must scan the entire stored list to count how many times each required corner point appears. This is redundant work — we repeatedly traverse the same list asking the same type of question: "how many copies of point (x, y) exist?"

With up to 3000 total calls and coordinates ranging from 0 to 1000, the stored list can grow to nearly 3000 points. An O(n²) count operation would perform up to 9 million iterations per query, which is borderline for time constraints.

The fundamental problem is that checking whether a specific point exists (and how many times) takes O(n) with a plain list. If we could answer "how many copies of (x, y) are stored?" in O(1) time, each horizontal partner would only require constant-time corner verification instead of O(n) scans.

This is exactly what a hash map provides — O(1) average-case lookups. By organizing our stored points into a nested hash map indexed by coordinates, we can replace every O(n) scan with an O(1) lookup, reducing the total count cost from O(n²) to O(n).

Optimal Approach - Hash Map Point Counting

Intuition

The key insight is to replace the expensive list scanning with O(1) hash map lookups. Instead of storing points in a flat list, we maintain a nested hash map cnt[x][y] that records how many times each specific coordinate has been added.

Think of it like organizing a library not by the order books arrive, but by their shelf and position. Instead of walking through every book to find one at shelf 3, position 10, you go directly to shelf 3 and check position 10 — instant lookup.

With this structure, the count operation becomes elegant:

For the query point (x1, y1), iterate through all unique x-coordinates stored in the map.
For each x2 ≠ x1, the signed distance d = x2 − x1 is the potential side length.
Check two possible squares:
- Direction 1 (y + d): corners at (x2, y1), (x1, y1 + d), (x2, y1 + d)
- Direction 2 (y − d): corners at (x2, y1), (x1, y1 − d), (x2, y1 − d)
For each direction, multiply the counts of all three corners — this naturally handles duplicates.

Using the signed distance d (not absolute value) is crucial. When x2 < x1, d is negative, so y1 + d gives a smaller y-value and y1 − d gives a larger one. This ensures we check both upward and downward squares regardless of whether the partner is to the left or right.

Step-by-Step Explanation

Let's trace count([11, 10]) after adding (3, 10), (11, 2), and (3, 2).

Hash map state: cnt = {3: {10: 1, 2: 1}, 11: {2: 1}}

Step 1: Query point is (11, 10). Initialize result = 0. We iterate over all unique x-coordinates in the map: {3, 11}.

Step 2: Consider x2 = 3 (since 3 ≠ 11). Compute d = 3 − 11 = −8.

Step 3: Look up the horizontal partner: cnt[3][10] = 1. A point at (3, 10) exists, confirming we have a valid horizontal edge.

Step 4: Check Direction 1 (y + d = 10 + (−8) = 2): Look up cnt[11][2] = 1 and cnt[3][2] = 1. Product = cnt[3][10] × cnt[11][2] × cnt[3][2] = 1 × 1 × 1 = 1. One valid square found with corners at (11, 10), (3, 10), (11, 2), (3, 2).

Step 5: Check Direction 2 (y − d = 10 − (−8) = 18): Look up cnt[11][18] = 0. No point exists at (11, 18). Product = 1 × 0 × 0 = 0. No squares in this direction.

Step 6: Skip x2 = 11 since x2 == x1 (side length would be 0, giving a degenerate square).

Step 7: All x-coordinates processed. Total result = 1 + 0 = 1.

Optimal — Hash Map O(1) Lookups for Square Detection — Watch how the hash map enables instant point-count lookups, replacing the brute force's O(n) list scans with O(1) checks for each potential square corner.

Algorithm

Data Structure: A nested hash map cnt where cnt[x][y] stores the count of point (x, y).

add(point):

Extract x, y from the point.
Increment cnt[x][y] by 1.

count(point):

Let the query point be (x1, y1). Initialize result = 0.
For each unique x-coordinate x2 in the hash map where x2 ≠ x1:
- Compute signed distance d = x2 − x1.
- Direction 1 (y1 + d): result += cnt[x2][y1] × cnt[x1][y1 + d] × cnt[x2][y1 + d]
- Direction 2 (y1 − d): result += cnt[x2][y1] × cnt[x1][y1 − d] × cnt[x2][y1 − d]
Return result.

Why signed distance matters: Using d = x2 − x1 (not abs(x2 − x1)) ensures that y1 + d and y1 − d naturally cover both upward and downward squares regardless of whether x2 is to the left or right of x1.

Code

#include <unordered_map>
#include <vector>
using namespace std;

class DetectSquares {
    unordered_map<int, unordered_map<int, int>> cnt;

    int getCount(int x, int y) {
        if (cnt.count(x) && cnt[x].count(y))
            return cnt[x][y];
        return 0;
    }

public:
    DetectSquares() {}

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

    int count(vector<int> point) {
        int x1 = point[0], y1 = point[1];
        int result = 0;
        for (auto& [x2, yMap] : cnt) {
            if (x2 != x1) {
                int d = x2 - x1;
                result += getCount(x2, y1) * getCount(x1, y1 + d)
                          * getCount(x2, y1 + d);
                result += getCount(x2, y1) * getCount(x1, y1 - d)
                          * getCount(x2, y1 - d);
            }
        }
        return result;
    }
};

from collections import defaultdict, Counter

class DetectSquares:
    def __init__(self):
        self.cnt = defaultdict(Counter)

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

    def count(self, point: list[int]) -> int:
        x1, y1 = point
        if x1 not in self.cnt:
            return 0
        result = 0
        for x2 in list(self.cnt.keys()):
            if x2 != x1:
                d = x2 - x1
                result += (self.cnt[x2][y1] *
                           self.cnt[x1][y1 + d] *
                           self.cnt[x2][y1 + d])
                result += (self.cnt[x2][y1] *
                           self.cnt[x1][y1 - d] *
                           self.cnt[x2][y1 - d])
        return result

import java.util.*;

class DetectSquares {
    private Map<Integer, Map<Integer, Integer>> cnt;

    public DetectSquares() {
        cnt = new HashMap<>();
    }

    public void add(int[] point) {
        cnt.computeIfAbsent(point[0], k -> new HashMap<>())
           .merge(point[1], 1, Integer::sum);
    }

    private int getCount(int x, int y) {
        return cnt.getOrDefault(x, Collections.emptyMap())
                  .getOrDefault(y, 0);
    }

    public int count(int[] point) {
        int x1 = point[0], y1 = point[1];
        int result = 0;
        for (int x2 : new ArrayList<>(cnt.keySet())) {
            if (x2 != x1) {
                int d = x2 - x1;
                result += getCount(x2, y1) * getCount(x1, y1 + d)
                          * getCount(x2, y1 + d);
                result += getCount(x2, y1) * getCount(x1, y1 - d)
                          * getCount(x2, y1 - d);
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity:

add: O(1) — a single hash map insertion/increment.
count: O(k) where k is the number of unique x-coordinates stored (k ≤ n).
- We iterate through all unique x-coordinates once.
- For each x-coordinate, we perform a constant number of O(1) hash map lookups (at most 6 lookups per x-coordinate: one for the horizontal partner, two for direction 1 corners, and two for direction 2 corners, plus the partner is shared).
- In the worst case, every stored point has a unique x-coordinate, so k = n and the total is O(n). But in practice, many points share x-coordinates, making k much smaller.

Space Complexity: O(n)

The nested hash map stores one entry per unique (x, y) coordinate pair. In the worst case, all n added points are distinct, requiring O(n) entries. Each entry stores a count integer, so the total space is O(n).

Comparison with Brute Force:

Brute Force count: O(n²) — for each horizontal partner, scan the full list O(n) to count corners.
Optimal count: O(n) — iterate unique x-coordinates, O(1) hash map lookups for corners.
The hash map converts repeated O(n) existence/count checks into O(1) lookups, saving a full factor of n.