947. Most Stones Removed with Same Row or Column LeetCode Solution
In this guide, you will get 947. Most Stones Removed with Same Row or Column LeetCode Solution with the best time and space complexity. The solution to Most Stones Removed with Same Row or Column problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Most Stones Removed with Same Row or Column
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.
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.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
947. Most Stones Removed with Same Row or Column LeetCode Solution in C++
class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
int numOfIslands = 0;
vector<vector<int>> graph(stones.size());
unordered_set<int> seen;
for (int i = 0; i < stones.size(); ++i)
for (int j = i + 1; j < stones.size(); ++j)
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
graph[i].push_back(j);
graph[j].push_back(i);
}
for (int i = 0; i < stones.size(); ++i)
if (seen.insert(i).second) {
dfs(graph, i, seen);
++numOfIslands;
}
return stones.size() - numOfIslands;
}
private:
void dfs(const vector<vector<int>>& graph, int u, unordered_set<int>& seen) {
for (const int v : graph[u])
if (seen.insert(v).second)
dfs(graph, v, seen);
}
}; /* code provided by PROGIEZ */
947. Most Stones Removed with Same Row or Column LeetCode Solution in Java
class Solution {
public int removeStones(int[][] stones) {
int numOfIslands = 0;
List<Integer>[] graph = new List[stones.length];
Set<Integer> seen = new HashSet<>();
for (int i = 0; i < graph.length; ++i)
graph[i] = new ArrayList<>();
for (int i = 0; i < stones.length; ++i)
for (int j = i + 1; j < stones.length; ++j)
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
graph[i].add(j);
graph[j].add(i);
}
for (int i = 0; i < stones.length; ++i)
if (seen.add(i)) {
dfs(graph, i, seen);
++numOfIslands;
}
return stones.length - numOfIslands;
}
private void dfs(List<Integer>[] graph, int u, Set<Integer> seen) {
for (final int v : graph[u])
if (seen.add(v))
dfs(graph, v, seen);
}
} // code provided by PROGIEZ
947. Most Stones Removed with Same Row or Column LeetCode Solution in Python
