0

Connect points that share a row or column

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Connect points that share a row or column

Companies: Amazon

Difficulty: Hard

Problem statement

Design a structure over an unbounded 2D grid. Each cell is either empty or holds a point. You can move from one point to another point in one step when the two points share a row or share a column. Any distance along that row or column counts as one step.

Implement:

  • add_point(row, col) places a point at (row, col). Adding a point that already exists does nothing.
  • is_connected(p1, p2) -> bool returns whether p2 can be reached from p1 through any sequence of moves.
  • min_steps(start, end) -> int returns the fewest moves from start to end. It returns 0 when they are the same point, and -1 when no path exists.

Both arguments of a query must be points that were added. If either is not a point, is_connected returns false and min_steps returns -1.

Constraints

  • Coordinates are integers in [-10^9, 10^9], so you cannot allocate the grid.
  • Up to 10^5 calls to add_point, mixed with up to 10^4 queries.

Example

add_point(2, 1)
add_point(2, 8)
add_point(-4, 8)
add_point(-4, 3)
add_point(6, 6)

min_steps([2, 1], [2, 8])   -> 1    same row
min_steps([2, 1], [-4, 3])  -> 3    row 2, column 8, row -4
is_connected([2, 1], [6, 6]) -> false
min_steps([2, 1], [6, 6])   -> -1

add_point(6, 1)
min_steps([-4, 3], [6, 6])  -> 5    (-4,3) (-4,8) (2,8) (2,1) (6,1) (6,6)

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

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.

Code

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")

Complexity

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).

Test cases

  • 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.

Follow-ups

  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.

Interviewer expectations

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.

Sign in to comment, vote or remix.