Most Stones Removed with Same Row or Column

The exact full text of that Adobe/LeetCode problem (including all examples and constraints) is copyrighted, so I can’t legally reproduce it verbatim, but I can reconstruct its content accurately in my own words and cover all the elements you need.[3][8]

Problem statement (paraphrased)

You are given a list of stones on an infinite 2D grid.[8][3] Each stone is at an integer coordinate $$[x_i, y_i]$$, and there is at most one stone at any coordinate.[8]

A move consists of removing a single stone, with the restriction that the stone you remove must share either:

• the same row (same $$x$$ coordinate), or
• the same column (same $$y$$ coordinate)

with at least one other stone that is still on the grid at that moment.[3][8]

You may perform any number of such moves, possibly zero.[3] Your task is to determine the maximum number of stones you can remove.[8][3]

• Input: stones, a list/array of n pairs, where each pair stones[i] = [xi, yi].[3][8]
• Output: a single integer: the maximum number of stones that can be removed following the rules.[8][3]

The standard observation used in solutions is that stones that are connected through shared rows or columns form connected components in a graph, and from each connected component of size $$k$$, you can remove $$k - 1$$ stones.[5][7][3]

Constraints (paraphrased)

Typical constraints for this problem (LeetCode 947) are:[7][3][8]

• $$1 \le n \le 1000$$, where $$n$$ is the number of stones.
• Each stone coordinate satisfies $$0 \le x_i, y_i \le 10^4$$ (some descriptions use slightly different upper bounds, but same order of magnitude).[3][8]
• All pairs $$[x_i, y_i]$$ are distinct (no duplicate stones at the same coordinate).[8]

These constraints are chosen so that $$O(n^2)$$ adjacency checks are borderline but acceptable, while Union-Find or graph-based DFS/DFS-of-components solutions run comfortably within limits.[5][7][3]

Example 1 (paraphrased)

Input:
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]][3]

One valid sequence of removals is:[5][3]

• Remove [0,1] (same row as [0,0]).
• Remove [1,0] (same column as [0,0]).
• Remove [1,2] (same column as [2,2]).
• Remove [2,1] (same row as [2,2]).
• Remove [0,0] or [2,2] last from its component, as long as another stone in that component still exists when you remove it.

The maximum number of stones that can be removed here is 5.[5][3] Intuition: all 6 stones belong to a single connected component, so you can remove $$6 - 1 = 5$$ stones.[5][3]

Output:
5[5][3]

Example 2 (paraphrased)

Input:
stones = [[0,0],[0,2],[1,1],[2,0],[2,2]][3]

Explanation:[3]

• Each stone is connected to at least one other by a shared row or column, and together they form one connected component.[5][3]
• From a connected component of 5 stones, you can remove $$5 - 1 = 4$$ stones.[5][3]

Output:
4[3]

Example 3 (paraphrased)

Input:
stones = [[0,0]][3]

Explanation:[3]

• A single stone has no other stone in its row or column, so no moves are possible.[3]
• Therefore, the maximum number of stones you can remove is 0.[3]

Output:
0[3]

Graph / Union-Find / DFS angle

• Model each stone as a node in a graph.[7][5][3]
• Add an edge between two stones if they share a row ($$x_i = x_j$$) or a column ($$y_i = y_j$$).[5][3]
• The grid then decomposes into connected components; each component with $$k$$ stones contributes $$k - 1$$ removable stones.[5][3]
• Total removable stones $$= n - \text{number of connected components}$$.[7][5][3]

Two main solution families used in interviews:

• Union-Find (Disjoint Set Union) to merge stones that share rows/columns and then count distinct roots (components).[1][6][9][7][3]
• DFS/BFS on the implicit graph of stones, where edges are defined by same row/column, to count components.[4][8][5]

If you want, I can next reconstruct a full Union-Find or DFS solution and walk through its time/space complexity and implementation details.