Last Updated: 30 Mar, 2021
Most Stones Removed with Same Row or Column
Hard
Asked in companies
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.
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.
Approaches
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:
- 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.
- 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’.