947. 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.

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.

Approach 01:

#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 numStones is 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 numNodes is the total number of stones and numEdges represents 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 visitedNodes set 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.