Most Stones Removed with Same Row or Column

Hard
0/120
Average time to solve is 45m
profile
Contributed by
18 upvotes
Asked in companies
SamsungAmazonPhonePe

Problem statement

On a 2-D 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.


You are given an array 'stones' of length 'n' where 'stones[i]' = '[ri, ci]' represent the ith stone’s location i.e 'ri' is the row coordinate of the 'ith' stone and 'ci' is the column coordinate of the 'ith' stone. Your task is to return the largest possible number of stones that can be removed.


Example: 
Input: 'stones' = [[0,1] [1,0] [0,0]]

Output: 2

Explanation:
We can remove the 1st stone at [0,1] as it has the same row as the 3rd stone [0, 0]. And remove the 2nd stone because it has the same column [0,1] as the 3rd stone.


Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains a single integer 'n', which represents the number of stones.

The following 'n' lines of the input contain the coordinates of the stones, where each line contains two space-separated integers representing the row and column, respectively.


Output format: 
Return a single line containing a single integer denoting the maximum number of stones that can be removed.


Note : 
You don't have to print anything. It's been already taken care of. Just implement the given function.
Sample Input 1 :
5
2 0
2 1 
3 1
3 2
5 5


Expected Answer:
3


Output on console:
3


Explanation of the Sample Input 1:
For this test case:
The answer will be 3: 
We can remove the stone at [2,1] because it has the same row as the stone [2,0], stone at [3,1] because it has the same column as [2,1] and stone at [3,2] because it shares the same row as [3,1].


Sample Input 2 :
1
1 1


Expected Answer:
0


Output on console:
0


Expected Time Complexity:
Try to do this in O(n*log(n)).


Constraints:

1 <= n <= 10^4
0 <= stones[i][j] <= 10^3

Time limit: 1 second
Hint

Can we find connected components via DSU?

Approaches (1)
Using DSU

The main idea is to use a DSU data structure, to find connected components. A DSU data structure can be used to maintain knowledge of the connected components of a graph, and query for them quickly. In particular, we would like to support two operations:

  1. find(node x), which outputs a unique id so that two nodes have the same id if and only if they are in the same connected component.
  2. union(node x, node y), which draws an edge (x, y) in the graph, connecting the components with id find(x) and find(y) together.

 

Following are the steps : 

  • Imagine each stone has an ID corresponding to its index in the input array.

 

  • Maintain two maps of pair (int, vector<int>),  ‘rowmap’ and ‘colmap’, which stores the id of the ith stone.

 

  • Map each occupied row to a vector of all stone IDs in that row.

 

  • Map each occupied column to a vector of all stone IDs in that column.

 

  • Maintain a ‘parent’ array that stores the parent of the ith node in the ‘ith’ index.

 

  • Union each stone ID with all other stone IDs in the same row or in the same column.

 

  • The union between two nodes is done in the following way:
    • Find the parent of the nodes.
    • If they have the same parent we do nothing.
    • Else we change the parent of one node to other.

 

  • Maintain a set ‘unique’ that stores the parent of the unique connected components.

 

  • Each connected group can have all but one stone removed. Thus, we count the number of unique groups and subtract this from the total number of stones to get our ‘answer’.

 

  • Return ‘answer’.
Time Complexity

O(N * log(N)), where ‘N’ is the size of the array.

 

We make ‘N’ queries for union which take at worst log(N) time, hence O(N * log(N).

Space Complexity

O(N), where ‘N’ is the size of the array.

 

Since we are keeping track of the parent nodes, which is equal to the size of the array, hence space complexity: O(N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Most Stones Removed with Same Row or Column
Full screen
Console