Day 51 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/minimize-connections/1

Maximum Stone Removal

Difficulty: Medium Accuracy: 49.82%

Given an 2D array of non-negative integers stones[][] where stones[i] = [xi , yi] represents the location of the ith stone on a 2D plane, the task is to return the maximum possible number of stones that you can remove.
A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.
Note: Each coordinate point may have at most one stone.
Examples:
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 any 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 remove 3 stones 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 any row/column with another stone still on the plane. Constraints: 1 ≤ stones.size() ≤ 1000 0 ≤ xi, yi ≤ 104 No two stones are at same position.

Solution:
class Solution:
def maxRemove(self, stones):
n = len(stones)
graph = {i: [] for i in range(n)}

    for i in range(n):
        for j in range(i+1, n):
            if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
                graph[i].append(j)
                graph[j].append(i)

    visited = set()

    def dfs(i):
        stack = [i]
        while stack:
            node = stack.pop()
            if node not in visited:
                visited.add(node)
                for nei in graph[node]:
                    if nei not in visited:
                        stack.append(nei)

    components = 0
    for i in range(n):
        if i not in visited:
            dfs(i)
            components += 1

    return n - components