Most Stones Removed with Same Row or Column LeetCode Solution

Problem Statement

Most Stones Removed with Same Row or Column LeetCode Solution says that 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.  An array stones of length n where stones[i] = [x_i, y_i] represents the location of the i^th stone. We have to find the largest number of stones to 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 <= x_i, y_i <= 10⁴
• No two stones are at the same coordinate point.

Approach

Idea

1. The idea here is that we can remove all stones from the group of connected stones except the last one.
2. If stone a and stone b are in the same column/row, we connect them as a component. That means we can make them as connected components.
3. The maximum number of stones can be removed = the number of stones-connected components.
4. For finding the connected components we can use DFS/BFS or Union find algorithms.

Code

C++ Solution

class Solution {
public:
    #define ll int
    ll par[10005];
    void make()
    {
        ll i;
        for(i=0;i<=10000;i++)
            par[i]=i;
    }
    ll find(ll x)
{
   if(par[x]==x)return x;
  return par[x]=find(par[x]);
}
    ll unite(ll x,ll y)
    {
        ll p1=find(x);
        ll p2=find(y);
        if(p1!=p2)
        {
            par[p1]=p2;
        }
        return 0;
    }
    int removeStones(vector<vector<int>>& stones) {
        make();
        set<ll>s;
        ll i,j,n=stones.size();
        for(i=0;i<n;i++)
        {
            
           for(j=i+1;j<n;j++)
           {
               
               if(stones[i][0]==stones[j][0] or stones[i][1]==stones[j][1])
               {
                   unite(i,j);
               }
           }
        }
        ll cnt=0;
        for(i=0;i<n;i++)
        {
            if(par[i]==i)cnt++;
        }
        return stones.size()-cnt;
    }
};

Java Solution

class Solution {
    int[] par=new int[10005];
    void make()
    {
        int i;
        for(i=0;i<=10000;i++)
            par[i]=i;
    }
    
    
    int find(int x)
  {
   if(par[x]==x)
    return x;
  return par[x]=find(par[x]);
   }
    
    
    int unite(int x,int y)
    {
        int p1=find(x);
        int p2=find(y);
        if(p1!=p2)
        {
            par[p2]=p1;
        }
        return 0;
    }
    public int removeStones(int[][] stones) {
        int i,j,n=stones.length;
        make();
        
        for(i=0;i<n;i++)
        {
            
           for(j=i+1;j<n;j++)
           {
               
               if(stones[i][0]==stones[j][0] || stones[i][1]==stones[j][1])
               {
                   unite(i,j);
               }
           }
        }
        int cnt=0;
        for(i=0;i<n;i++)
        {
            if(par[i]==i)cnt++;
        }
        int k=n-cnt;
        return k;
        
    }
}

Complexity Analysis of Most Stones Removed with Same Row or Column LeetCode Solution

Time Complexity

Time complexity is O(N*N). As we are looping in the array to connect them. Where N is the array size.

Space Complexity

Space complexity is 0(N). We are taking extra space to store the parents.