The Most Stones Removed with Same Row or Column problem places stones on a 2D grid. Two stones can be "connected" if they share a row or column. You can remove any stone that belongs to a connected group of at least 2 stones. Find the maximum number of stones that can be removed. This Most Stones Removed with Same Row or Column coding problem uses Union-Find or DFS to count connected components.
Microsoft, Meta, Amazon, Google, and Bloomberg ask this because the key insight — that you can remove all stones in a connected component except one — converts the problem from a simulation to a component-counting exercise. The union find, hash table, graph, and DFS interview pattern is central, and recognizing this mathematical insight is what separates strong candidates.
Union-Find on shared row/column. Use Union-Find where stones sharing a row or column are in the same component. The number of removable stones = total stones - number of connected components. To efficiently handle potentially large row/column indices, use a hash map for Union-Find instead of an array.
Stones: [(0,0), (0,1), (1,0), (2,2)].
Problems about "connected groups where connectivity is defined by shared attribute" are textbook Union-Find. Here, two stones are connected if they share a row or column. The final answer — remove all but one per component — follows from the fact that you can always chain removals within a component. Practice Union-Find with hash map implementations for large coordinate spaces. The answer formula total - components appears in many similar graph connectivity problems.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Minimize Malware Spread | Hard | Solve | |
| Redundant Connection | Medium | Solve | |
| Graph Valid Tree | Medium | Solve | |
| Minimize Malware Spread II | Hard | Solve | |
| Is Graph Bipartite? | Medium | Solve |
