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 <= 10000 <= xi, yi <= 104- No two stones are at the same coordinate point.
Approach 01:
-
C++
-
Python
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
int islandCount = 0; // To count the number of connected components (islands)
vector<vector<int>> adjacencyList(stones.size()); // Graph represented as an adjacency list
unordered_set<int> visitedNodes; // Set to keep track of visited nodes
// Building the graph by connecting nodes that are in the same row or column
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]) {
adjacencyList[i].push_back(j);
adjacencyList[j].push_back(i);
}
}
}
// DFS to count the number of islands (connected components)
for (int i = 0; i < stones.size(); ++i) {
if (visitedNodes.insert(i).second) { // If node i is not visited
exploreConnectedComponent(adjacencyList, i, visitedNodes);
++islandCount; // Increment the count of islands
}
}
// The answer is the total number of stones minus the number of connected components
return stones.size() - islandCount;
}
private:
void exploreConnectedComponent(const vector<vector<int>>& adjacencyList, int node, unordered_set<int>& visitedNodes) {
for (const int adjacentNode : adjacencyList[node]) {
if (visitedNodes.insert(adjacentNode).second) { // If adjacentNode is not visited
exploreConnectedComponent(adjacencyList, adjacentNode, visitedNodes); // Continue DFS
}
}
}
};
from typing import List, Set
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
islandCount = 0 # To count the number of connected components (islands)
adjacencyList = [[] for _ in range(len(stones))] # Graph represented as an adjacency list
visitedNodes: Set[int] = set() # Set to keep track of visited nodes
# Building the graph by connecting nodes that are in the same row or column
for i in range(len(stones)):
for j in range(i + 1, len(stones)):
if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
adjacencyList[i].append(j)
adjacencyList[j].append(i)
# DFS to count the number of islands (connected components)
for i in range(len(stones)):
if i not in visitedNodes: # If node i is not visited
self.exploreConnectedComponent(adjacencyList, i, visitedNodes)
islandCount += 1 # Increment the count of islands
# The answer is the total number of stones minus the number of connected components
return len(stones) - islandCount
def exploreConnectedComponent(self, adjacencyList: List[List[int]], node: int, visitedNodes: Set[int]) -> None:
for adjacentNode in adjacencyList[node]:
if adjacentNode not in visitedNodes: # If adjacentNode is not visited
visitedNodes.add(adjacentNode)
self.exploreConnectedComponent(adjacencyList, adjacentNode, visitedNodes) # Continue DFS
Time Complexity
- Building the Graph:
Constructing the adjacency list requires comparing each pair of stones to check if they share the same row or column. This process involves iterating through all pairs of stones, resulting in \( O(\text{numStones}^2) \) time complexity, where
numStonesis the total number of stones. - Depth-First Search (DFS):
The DFS traversal visits each node and its neighbors once. The time complexity of DFS is \( O(\text{numNodes} + \text{numEdges}) \), where
numNodesis the total number of stones andnumEdgesrepresents the total edges in the adjacency list. - Overall Time Complexity:
The overall time complexity is dominated by the graph construction step, resulting in \( O(\text{numStones}^2) \).
Space Complexity
- Adjacency List:
The adjacency list stores connections between stones that share the same row or column. In the worst case, each stone could be connected to all other stones, leading to \( O(\text{numStones}^2) \) space.
- Visited Nodes Set:
The
visitedNodesset keeps track of visited nodes, requiring \( O(\text{numStones}) \) space. - Recursive Call Stack:
The recursive DFS calls can go as deep as the number of stones in the worst case, adding an additional space complexity of \( O(\text{numStones}) \).
- Overall Space Complexity:
The overall space complexity is \( O(\text{numStones}^2) \), dominated by the adjacency list.