947. Most Stones Removed with Same Row or Column
Most Stones Removed with Same Row or Column (LeetCode 947) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
How to solve Most Stones Removed with Same Row or Column
Most Stones Removed with Same Row or Column is a Union-Find problem, part of Graph Traversal Patterns (DFS & BFS). Master Union-Find data structure with path compression and union by rank for connectivity problems.
Work towards the solution in these steps:
- Think about representing the stones as nodes in a graph where an edge connects stones sharing the same row or column.
- Consider using a graph traversal method like DFS or BFS to identify connected components of stones.
- Each connected component represents stones connected through shared rows or columns, allowing removal of all but one stone in that component.
The reference solution runs in O(n) time and O(n) space.
The Most Stones Removed with Same Row or Column solution and editorial walks through the full approach with reference code.
Problem statement
On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.
A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.
Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] Output: 5 Explanation: One way to remove 5 stones is as follows: 1. Remove stone [2,2] because it shares the same row as [2,1]. 2. Remove stone [2,1] because it shares the same column as [0,1]. 3. Remove stone [1,2] because it shares the same row as [1,0]. 4. Remove stone [1,0] because it shares the same column as [0,0]. 5. Remove stone [0,1] because it shares the same row as [0,0]. Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.
Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] Output: 3 Explanation: One way to make 3 moves is as follows: 1. Remove stone [2,2] because it shares the same row as [2,0]. 2. Remove stone [2,0] because it shares the same column as [0,0]. 3. Remove stone [0,2] because it shares the same row as [0,0]. Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.
Example 3:
Input: stones = [[0,0]] Output: 0 Explanation: [0,0] is the only stone on the plane, so you cannot remove it.
Constraints:
- 1 <= stones.length <= 1000
- 0 <= xi, yi <= 104
- No two stones are at the same coordinate point.
Topics and companies
Topics: Hash Table, Depth-First Search, Union Find, Graph.
Reported in interviews at Google.
How to practise Most Stones Removed with Same Row or Column on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.
Open Most Stones Removed with Same Row or Column in the code editor, or read the Most Stones Removed with Same Row or Column editorial for a worked solution with its approach and complexity analysis.
Where Most Stones Removed with Same Row or Column sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Union-Find (Disjoint Set Union - DSU) subpattern
- The full DSA patterns sheet
Problems related to Most Stones Removed with Same Row or Column
Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:
- Accounts Merge — Medium, same subpattern
- Graph Valid Tree — Medium, same subpattern
- Greatest Common Divisor Traversal — Hard, same subpattern
- Largest Component Size by Common Factor — Hard, same subpattern
- Number of Connected Components in an Undirected Graph — Medium, same subpattern
- Number of Islands II — Hard, same subpattern
Most Stones Removed with Same Row or Column FAQ
What is the LeetCode number of Most Stones Removed with Same Row or Column?
Most Stones Removed with Same Row or Column is LeetCode problem 947, rated Medium.
What pattern is used to solve Most Stones Removed with Same Row or Column?
Most Stones Removed with Same Row or Column is a Union-Find problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
What is the time complexity of Most Stones Removed with Same Row or Column?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Most Stones Removed with Same Row or Column?
Most Stones Removed with Same Row or Column has been reported in interviews at Google.