Connect points that share a row or column

Think of the points as nodes of a graph: two points share an edge when they
sit in the same row or the same column. is_connected asks whether two nodes
are in the same component, and min_steps asks for the unweighted shortest
path between them. The matrix is unbounded, so we never allocate a grid; we
store only the points, indexed by row and by column.

Brute force. Keep a list of points. For a query, build the graph on the fly
(compare every pair, O(P^2) edges in the worst case) and run BFS. It is correct
and a fine place to start, but one long row of k points already yields
k^2 / 2 edges, and every query pays for it again.

Connectivity: union-find over lines, not over pairs. The trick is to stop
thinking of point-to-point edges. A point connects its row and its column, so
give every row r a node ("r", r) and every column c a node ("c", c).
add_point(r, c) does one union(("r", r), ("c", c)). Two points are connected
exactly when their rows are in the same set: a path of moves alternates between
sharing rows and sharing columns, and every point on the path glues its row to
its column. With path compression and union by size, both add_point and
is_connected are effectively O(1) (inverse Ackermann). This also handles the
"cliques" for free: a row with 1,000 points costs 1,000 unions, not 500,000.

Shortest path: BFS that consumes whole lines. A plain BFS that, for each
dequeued point, scans every point in its row and column is O(P^2) in the worst
case, because the same row gets scanned once per point in it. Fix: the first
time BFS reaches any point in row r, every unvisited point in that row is
reached at the very next step. So mark the row as used the first time we
expand it and never expand it again; the same for columns. Each row list and
column list is scanned once, so a query is O(P) after the indexes exist.

Invariants:

• rows[r] and cols[c] hold every added point exactly once (duplicates are
  ignored).
• In BFS, a point's distance is final when it is first enqueued (unit weights,
  FIFO order).
• A used row or column never needs another scan: all of its points were
  enqueued at d + 1 when it was first expanded at distance d, which is the
  smallest distance any of them can get.

Before running BFS we check the union-find: if the points are not connected we
return -1 immediately, which is the common case for "impossible" queries.

from collections import deque
from typing import Dict, Hashable, List, Sequence, Set, Tuple

Point = Tuple[int, int]


class DSU:
    def __init__(self) -> None:
        self.parent: Dict[Hashable, Hashable] = {}
        self.size: Dict[Hashable, int] = {}

    def add(self, x: Hashable) -> None:
        if x not in self.parent:
            self.parent[x] = x
            self.size[x] = 1

    def find(self, x: Hashable) -> Hashable:
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:  # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a: Hashable, b: Hashable) -> None:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]


class PointGrid:
    def __init__(self) -> None:
        self.points: Set[Point] = set()
        self.rows: Dict[int, List[Point]] = {}
        self.cols: Dict[int, List[Point]] = {}
        self.dsu = DSU()

    def add_point(self, row: int, col: int) -> None:
        p = (row, col)
        if p in self.points:
            return
        self.points.add(p)
        self.rows.setdefault(row, []).append(p)
        self.cols.setdefault(col, []).append(p)
        rk, ck = ("r", row), ("c", col)
        self.dsu.add(rk)
        self.dsu.add(ck)
        self.dsu.union(rk, ck)

    def is_connected(self, p1: Sequence[int], p2: Sequence[int]) -> bool:
        a, b = (p1[0], p1[1]), (p2[0], p2[1])
        if a not in self.points or b not in self.points:
            return False
        return self.dsu.find(("r", a[0])) == self.dsu.find(("r", b[0]))

    def min_steps(self, start: Sequence[int], end: Sequence[int]) -> int:
        s, t = (start[0], start[1]), (end[0], end[1])
        if not self.is_connected(s, t):
            return -1
        if s == t:
            return 0
        dist: Dict[Point, int] = {s: 0}
        used_rows: Set[int] = set()
        used_cols: Set[int] = set()
        queue = deque([s])
        while queue:
            p = queue.popleft()
            d = dist[p]
            lines = []
            if p[0] not in used_rows:
                used_rows.add(p[0])
                lines.append(self.rows[p[0]])
            if p[1] not in used_cols:
                used_cols.add(p[1])
                lines.append(self.cols[p[1]])
            for line in lines:
                for q in line:
                    if q not in dist:
                        if q == t:
                            return d + 1
                        dist[q] = d + 1
                        queue.append(q)
        return -1  # unreachable when the DSU says connected


if __name__ == "__main__":
    g = PointGrid()
    for r, c in [(0, 0), (0, 5), (3, 5), (3, -2), (10, 10)]:
        g.add_point(r, c)
    assert g.is_connected([0, 0], [3, -2])
    assert g.min_steps([0, 0], [3, -2]) == 3
    assert g.min_steps([0, 0], [0, 5]) == 1
    assert g.min_steps([3, 5], [3, 5]) == 0
    assert not g.is_connected([0, 0], [10, 10])
    assert g.min_steps([0, 0], [10, 10]) == -1
    assert g.min_steps([0, 0], [7, 7]) == -1  # (7, 7) is not a point
    g.add_point(10, 0)  # bridges (10, 10) through column 0
    assert g.min_steps([0, 5], [10, 10]) == 3
    assert g.min_steps([3, -2], [10, 10]) == 5
    print("ok")

Let P be the number of points, R and C the distinct rows and columns.

• add_point: O(α(R + C)) amortized, effectively O(1). Space O(1) per point
  in the row/column indexes plus at most two DSU nodes.
• is_connected: O(α(R + C)), effectively O(1).
• min_steps: O(P + R + C) time and O(P) extra space per query. Each point is
  enqueued at most once, and each row and column list is scanned at most once.
  Only the component containing start is touched.
• Total space: O(P + R + C).

• Points (0,0) (0,5) (3,5) (3,-2): min_steps((0,0), (3,-2)) = 3
  (row 0, column 5, row 3); is_connected is True.
• Same row: min_steps((0,0), (0,5)) = 1.
• Same point: min_steps(p, p) = 0, is_connected(p, p) = True.
• Isolated point (10,10): is_connected((0,0), (10,10)) = False,
  min_steps = -1.
• A coordinate that was never added: is_connected is False, min_steps is
  -1.
• Adding (10,0) merges two components: afterwards
  min_steps((0,5), (10,10)) = 3 and min_steps((3,-2), (10,10)) = 5.
• Duplicate add_point(0, 0): no change in answers, no duplicate in the
  row/column lists.
• Negative and very large coordinates ((-10^9, 10^9)) work, since nothing is
  sized by the coordinate range.
• Stress: 10^5 points all in row 0; min_steps between any two is 1 and
  runs in linear time, not quadratic.

1. remove_point(row, col). Union-find cannot split sets. Options: answer
   is_connected with BFS on the line graph (O(P) per query), rebuild the DSU
   lazily after a batch of removals, or, if all operations are known up front,
   process them offline in reverse so removals become additions.
2. Many min_steps queries, few additions. Build the bipartite row/column
   graph once. A shortest path between points maps to a path in that graph:
   moves = 1 + number of line switches. Cache BFS results per source line, or
   run BFS from both ends (bidirectional) to cut the explored area.
3. Return the actual path. Store a parent pointer when a point is first
   enqueued and walk back from end. Same complexity.
4. Moves are limited to the nearest point in each direction (you cannot
   jump over a point). Keep each row and column sorted (a balanced tree or
   sortedcontainers), so each point has at most four neighbors found by
   binary search. BFS becomes O(P log P), and connectivity is unchanged because
   jumping over points does not change which points are reachable.
5. Count components or the largest connected group. Track the number of
   live DSU roots that own at least one point, and the point count per root;
   update both in add_point. This is LeetCode 947 (remove stones) in
   disguise: removable points = P - components.

Mid-level (L4)

• Models points as a graph with same-row/same-column edges and writes a correct
  BFS for min_steps, returning -1 and 0 in the right cases.
• Uses hash maps instead of a grid once the "unbounded" hint lands.
• Gets is_connected right, even if it reuses BFS.

Senior (L5)

• Indexes points by row and by column and spots the O(P^2) trap in naive BFS;
  fixes it by marking rows and columns as used.
• Uses union-find for is_connected with near-constant time, and explains why
  unioning a row with a column is enough.
• Covers duplicates, missing points, and same-point queries without prompting.

Staff (L6+)

• Frames the problem as a bipartite row/column graph and reasons about it in
  those terms (path length, components, LeetCode 947 relationship).
• Discusses read/write trade-offs: deletions breaking union-find, caching,
  offline processing, bidirectional BFS.
• Talks about scale: memory per point, very large coordinates, and how to shard
  or persist the indexes if this became a service.