Solution: Most Stones Removed with Same Row or Column

Let's solve the Most Stones Removed with Same Row or Column problem using the Union Find pattern.

We'll cover the following

Statement

Given an array of nn stones in a two-dimensional plane, where each stone is represented by a pair of x and y coordinates, find the maximum number of stones we can remove with the following condition:

A stone can be removed if it shares either the same row or the same column with another stone that has not been removed so far.

Stones are provided as an array, stones, of length nn, where stones[i]=[xi,yi]stones[i] = [x_i, y_i] represents the ithi^{th} stone. Return the maximum possible number of stones that can be removed.

Constraints:

  • 1≤1\leq stones.length ≤1000\leq 1000
  • 0≤xi,yi≤500\leq x_i, y_i \leq50

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time and any implementation constraints.

Naive approach

The naive approach to solve this problem would be to iterate over the stones and try to remove each stone one by one. For each stone, we’ll check if it shares a row or column with another stone, and if it does, we remove the stone and increment a counter. In this approach, the order of removing the stones matters, so we will have to check all the combinations to reach the maximum number of stones we can remove.

We’ll get the solution, but the cost of achieving this is very high since the time complexity of this approach is O(n2)O(n^2). This is because we have to check for each stone against every other stone. Let’s try to devise an optimized solution for this problem.

Optimized solution using union find

To avoid the cost of processing one stone at a time, we can work with a group of stones instead. For this, we combine all the stones that share the same row or column into a single group. Then, in any of these groups, if we try to remove all the stones except for one, it won’t violate the problem’s condition because each row and column still retains at least one stone. This implies that the number of distinct groups corresponds to the number of stones that can’t be removed from the grid. Then, it would be safe to say that the maximum number of stones that can be removed equals the total number of stones minus the number of groups formed. These groups are connected components if we use the Union Find pattern to achieve this.

Using the Union method, we iterate through each stone and merge stones that share the same row or column into single connected components. After processing all the stones, we get the count of distinct connected components. Finally, we subtract this count from the total number of stones, indicating the maximum number that can be removed without violating the problem’s constraint.

The algorithm works as follows:

  1. In the UnionFind class, we initialize the following:

    1. Two dictionaries, parents and ranks, to store the relevant information.

    2. union(x, y):

      1. This method takes x and y coordinates of a stone and assigns each coordinate as a parent of itself in the parents dictionary. It makes sure that the parent of the coordinate is updated only if it doesn't have an existing parent.

      2. Next, it merges the coordinates based on their rank values such that it attaches the lower rank coordinate to the higher rank coordinate. Otherwise, if both of the coordinates have the same rank, we choose either of the coordinates as the parent and attach the other coordinate to it.

      3. While merging, if the current child coordinate is already merged with another coordinate, we recursively find their root parent using the find() method. We set the current parent coordinate as the parent of the root.

      4. To attach any coordinate, c, as a child to a parent coordinate, p, we update the parents dictionary and set parents[c] = p. We also increment the rank of the parent coordinate, p, by 1 in the ranks dictionary.

    3. find(coordinate):

      1. This method takes a coordinate of a stone and returns its parent. It returns itself if the given coordinate is a parent of itself. Otherwise, it finds the parent of its parent recursively and returns it.

  2. Iterate over the stones, and perform union by calling the union() function on all of the stones. This will form the groups and add them to the parents dictionary. Since x and y can have the same values, e.g., [0,0] or [1,1], an offset value is added to the coordinate y to avoid any possible clash in the parents and ranks dictionaries.

  3. To get the number of groups, we find the root parent of each element of the parents dictionary using the find() method.

  4. In the end, we return the difference between the number of stones and the number of groups made.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s try to implement the algorithm as discussed above:

main.java
UnionFind.java
import java.util.*;
class RemoveStones {
    public static int removeStones(int[][] stones) {
        int offset = 100000;
        UnionFind stone = new UnionFind();
        for (int[] s : stones) {
            int x = s[0];
            int y = s[1];
            stone.union(x, y + offset);
        }
        Set<Integer> groups = new HashSet<>();
        Map<Integer, Integer> parents = stone.getParents();
        for (Map.Entry<Integer, Integer> entry : parents.entrySet()) {
            groups.add(stone.find(entry.getKey()));
        }
        return stones.length - groups.size();
    }
    // Driver code
    public static void main(String[] args) {
        int[][][] stones = {
        {{0, 0}, {0, 1}, {1, 2}, {2, 2}, {3, 3}},
        {{0, 0}, {2, 2}, {3, 3}},
        {{0, 1}, {2, 1}, {3, 0}},
        {{1, 0}, {2, 1}, {2, 3}, {3, 1}, {3, 3}},
        {{1, 2}, {2, 0}, {2, 2}, {3, 3}}
        };
        for (int i = 0; i < stones.length; i++) {
            System.out.println((i + 1) + ".\tMaximum stones which can be removed from " +
                    Arrays.deepToString(stones[i]) + " are: " + removeStones(stones[i]));
            System.out.println(String.join("", Collections.nCopies(100, "-")));
        }
    }
}
Most Stones Removed with Same Row or Column

Solution summary

To recap, the solution to this problem can be divided into the following three parts:

  1. Iterate over all the stones, and use the union() function to check if they share a row or column with other stones. Merge the stones into one group if they share a row or column.

  2. Use the find() function to get the number of groups to which the stones belong.

  3. Return the difference between the number of stones and the number of groups made.

Time complexity

The time complexity of this solution is O(n×α(n))O(n \times \alpha (n)), where nn is the number of coordinates given in input, and O(α(n))O(\alpha (n)) is the time taken for performing union by rank and path compression. α(n)\alpha (n) is almost constant time and grows very slowly with the input size.

Therefore, the overall time complexity becomes O(n)O(n).

Space complexity

The space complexity is O(n)O(n), where nn is the number of coordinates.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.