947. Most Stones Removed with Same Row or Column

MediumDepth-First SearchUnion FindGraphHash Table
Leetcode Link

Problem Description

In this problem, we're given n stones positioned at integer coordinate points in a 2-dimensional plane. The key rule is that no two stones can occupy the same coordinate point. A stone can be removed if there is at least one other stone sharing the same row or column on the grid, and that other stone is still on the plane (i.e., it hasn't been removed).

Our task is to find out the maximum number of stones that can be removed while following the stated rule. The stones are represented in an array named stones, with each element stones[i] being a list of 2 integers: [xi, yi], which corresponds to the location of the i-th stone on the 2D plane.

Flowchart Walkthrough

To determine the suitable algorithm for solving Leetcode 947. Most Stones Removed with Same Row or Column, let's use the flowchart provided. Here’s a detailed analysis using the flowchart:

Is it a graph?

  • Yes: In this problem, stones can be treated as nodes. An edge exists between two nodes if they lie in the same row or column. This transforms the problem into a graph where connected components need to be identified.

Is it a tree?

  • No: As the graph might have multiple connected components and cycles (stones in the same row or column), it does not have the hierarchical structure of a tree.

Is the problem related to directed acyclic graphs (DAGs)?

  • No: This problem involves identifying connected components in an undirected graph; it doesn’t concern acyclic properties or directed edges.

Is the problem related to shortest paths?

  • No: The task is to find and remove stones, not to calculate shortest paths between any two nodes.

Does the problem involve connectivity?

  • Yes: The crucial task here is to determine connected components. Each component represents a group of stones that can be reached from any other stone in that group.

Is the graph weighted?

  • No: Connections (edges) between stones either exist or don't based on their rows and columns, without any additional weighting criteria.

Conclusion: Since the primary requirement is to identify connected components in an unweighted graph, and the graph is not a tree or a DAG, the problem is well-suited for a Depth-First Search (DFS) approach where each DFS traversal would help identify and navigate through a complete connected component. DFS is effective for exploring each vertex and its adjacent nodes, which is needed for grouping stones that can be removed together.

Intuition

The intuition behind the solution begins by understanding that if two stones share the same row or the same column, they are part of the same connected component. In the context of the problem, connected components are groups of stones that are all connected by rows or columns in such a way that if you pick any stone in a connected component, you'd be able to trace to any other stone in the same connected component through shared rows or columns. The last stone in such a connected component can never be removed as there would be no other stone in the same row or column.

Now, the key observation is that the maximum number of stones that can be removed is equal to the total number of stones minus the number of these connected components. To illustrate, imagine you have three stones forming a straight line either horizontally or vertically. You can remove the two endpoint stones but have to leave the middle one, making the connected components count as one.

The provided Python solution employs the union-find (or disjoint-set) data structure to efficiently find connected components. This structure helps to keep track of elements that are connected in some way, and in this case, is used to identify stones that are in the same row or column.

Here's the breakdown of how the union-find algorithm is applied:

  1. Each stone is represented by a node, whose initial "parent" is itself, indicating that it is initially in its own connected component.
  2. Iterate over all stones. For each stone (x, y), unify the component containing x with the component containing y + n (we offset y by n to avoid collisions between row and column indices as they could be the same).
  3. After all stones have been iterated over, we count unique representatives of the connected components which are the parent nodes for the rows and columns.
  4. The answer is the total number of stones minus the number of unique representatives (connected components).

By applying union-find, the solution achieves a merging process of the stones that lie in the same connected component quickly, leading to an efficient way to calculate the maximum number of stones that can be removed.

Learn more about Depth-First Search, Union Find and Graph patterns.

Solution Approach

The solution implements a Union-Find data structure to keep track of connected components. This data structure is particularly useful in dealing with problems that involve grouping elements into disjoint sets where the connectivity between the elements is an essential attribute.

Here’s a step-by-step explanation of the solution:

Initialization

  • An array p is created with size 2*n. This is because we have n possible x-coordinates (0 to n-1) and n possible y-coordinates (0 to n-1), but we need to separate the representation to avoid collision, hence n is doubled. The array p represents the parent of each node, where a node is either a row or a column index.
  • Initially, every element is set to be its own parent.

The find function

  • The find function is a standard function in Union-Find, which returns the representative (root parent) of the disjoint set that x belongs to.
  • If x does not point to itself, we recursively find the parent of x until we reach the root while applying path compression. Path compression means we set p[x] to its root directly to flatten the structure, which speeds up future find operations on elements in the same set.

Unification Process

  • The main loop iterates over every stone.
  • For a given stone at coordinates (x, y), we unify the set containing x with the set containing y + n to ensure we don't mix up rows and columns.
  • The unification is done by setting the parent of the set containing x to be the parent of the set containing y + n using the find function.

Counting Connected Components

  • A set s is used to store unique parents of the stones, which comes from applying the find function on every stone's x-coordinate.
  • The number of unique parents indicates the number of connected components.

Calculating the Answer

  • Finally, the solution is the total number of stones minus the number of connected components. To see why this is the case, for each connected component, one stone will inevitably remain, making all others removable.
  • len(stones) - len(s) gives us the count of removable stones, satisfying the problem's requirement.

By implementing Union-Find, the solution approach efficiently identifies and unifies stones into connected components and calculates the maximum number of stones that can be removed, leading to an effective strategy for this problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example with 5 stones to illustrate the solution approach.

Assume we have n = 5 stones at the following coordinates on a 2D plane: [[0,0], [0,2], [1,1], [2,0], [2,2]]. So our stones array looks like this: stones = [[0,0], [0,2], [1,1], [2,0], [2,2]].

Steps According to the Solution Approach:

  1. Initialization: We create an array p of size 2*n = 10. This array will help us keep track of the parent of each coordinate considering both x and y coordinates.

  2. The find function: Let's define our find function which takes an index x and recursively finds the representative of x's set, while applying path compression.

  3. Unification Process:

    • Looking at stones[0] = [0,0], we unify the x-coordinate (0) with the y-coordinate (0 + 5) to avoid collision with the x-coordinates.
    • Then, stones[1] = [0,2], we unify 0 with 2 + 5.
    • For stones[2] = [1,1], we unify 1 with 1 + 5.
    • Next, stones[3] = [2,0], we unify 2 with 0 + 5.
    • Finally, stones[4] = [2,2], we unify 2 with 2 + 5.

  4. Counting Connected Components:

    • We keep a set s and insert the root parent for each x-coordinate after unification.
    • After the unification, we have root parents for the x-coordinates: [0, 1, 2]. Let's assume union-find identifies 0, 1, and 2 as the roots for our example, meaning we have 3 connected components.

  5. Calculating the Answer:

    • We have a total of 5 stones, and we've identified 3 connected components. The maximum number of stones that we can remove is len(stones) - len(s) which is 5 - 3 = 2. Thus, we can remove a maximum of 2 stones while ensuring that no stone is isolated.

This walkthrough demonstrates the solution approach using the union-find algorithm to efficiently compute the maximum number of stones that can be removed according to the given rules. By identifying the connected components where stones share the same row or column, union-find allows us to easily count these connected components and therefore calculate the maximum number of removable stones.

Solution Implementation

1class Solution:
2    def removeStones(self, stones: List[List[int]]) -> int:
3        def find_root(root_id):
4            """
5            Recursive function that finds the root of a disjoint set.
6            Path compression is applied to flatten the structure for efficiency.
7            """
8            if parent[root_id] != root_id:
9                parent[root_id] = find_root(parent[root_id])
10            return parent[root_id]
11
12        # Given the constraints of the problem, there can be at most 20000 nodes
13        # because stones could be placed in rows and columns 0 through 9999.
14        num_nodes = 10000
15        # Create an array representing the disjoint set forest with an initial parent of itself.
16        parent = list(range(num_nodes * 2))
17      
18        # Iterate through each stone and unify their row and column into the same set.
19        for x, y in stones:
20            parent[find_root(x)] = find_root(y + num_nodes)
21
22        # Use a set comprehension to store the unique roots of all stones' rows and columns.
23        unique_roots = {find_root(x) for x, _ in stones}
24      
25        # Calculate how many stones can be removed by subtracting the number of unique sets
26        # (which have to remain) from the total number of stones.
27        return len(stones) - len(unique_roots)
28
29# Note: This code assumes that the List class has been imported from the typing module:
30# from typing import List
31
1class Solution {
2    private int[] parent; // Array to represent the parent of each element in the Disjoint Set Union (DSU)
3
4    public int removeStones(int[][] stones) {
5        int n = 10010; // Representative value for scaling row and column indices
6        parent = new int[n << 1]; // Initialize the parent array for the DSU
7        for (int i = 0; i < parent.length; ++i) {
8            parent[i] = i; // Initially, each element is its own parent
9        }
10        for (int[] stone : stones) {
11            // Perform union of stone's row and column by setting the parent of the stone's row to the representative
12            // of the stone's adjusted column index
13            parent[find(stone[0])] = find(stone[1] + n);
14        }
15        Set<Integer> uniqueRoots = new HashSet<>(); // Set to store unique roots after unions have been performed
16        for (int[] stone : stones) {
17            // Add the representative of each stone's row to the set of unique roots
18            uniqueRoots.add(find(stone[0]));
19        }
20        // The number of stones that can be removed is the total number of stones minus the number of unique roots,
21        // since each root represents a connected component
22        return stones.length - uniqueRoots.size();
23    }
24
25    private int find(int x) {
26        // Recursively find the root representative of the element `x`. Path compression is applied here to flatten
27        // the structure of the tree, effectively speeding up future `find` operations.
28        if (parent[x] != x) {
29            parent[x] = find(parent[x]);
30        }
31        return parent[x];
32    }
33}
34
1class Solution {
2public:
3    // Class member to hold the parent pointers for the Union-Find data structure
4    vector<int> parents;
5
6    // Function to remove as many stones as possible while ensuring at least one
7    // stone is left in the same row or column
8    int removeStones(vector<vector<int>>& stones) {
9        // Define a large enough value for the maximum coordinate
10        int maxCoord = 10010;
11        // Resize the parents vector to double the value since we are mapping
12        // 2-D coordinates to a 1-D array
13        parents.resize(maxCoord << 1);
14        // Initialize the parent of each element to be itself
15        for (int i = 0; i < parents.size(); ++i) {
16            parents[i] = i;
17        }
18      
19        // Perform union operations for the stones
20        for (auto& stone : stones) {
21            parents[find(stone[0])] = find(stone[1] + maxCoord);
22        }
23      
24        // Using a set to store unique roots after path compression
25        unordered_set<int> uniqueRoots;
26        for (auto& stone : stones) {
27            uniqueRoots.insert(find(stone[0]));
28        }
29      
30        // The number of stones that can be removed is the total number of stones
31        // minus the number of unique roots in the disjoint-set forest
32        return stones.size() - uniqueRoots.size();
33    }
34
35    // Function to find the root of the element with path compression
36    int find(int x) {
37        if (parents[x] != x) {
38            parents[x] = find(parents[x]); // Path compression step
39        }
40        return parents[x];
41    }
42};
43
1// Type definition for a 2D point.
2type Point = [number, number];
3
4// Global variable to hold parent pointers for the disjoint-set (Union-Find) data structure.
5const parents: number[] = [];
6
7// Function to initialize 'parents' whereby each element is its own parent.
8function initParents(size: number): void {
9    for (let i = 0; i < size; i++) {
10        parents[i] = i;
11    }
12}
13
14// Function to find the root of element 'x' with path compression.
15function find(x: number): number {
16    if (parents[x] !== x) {
17        parents[x] = find(parents[x]); // Path compression step
18    }
19    return parents[x];
20}
21
22// Function to remove as many stones as possible while ensuring
23// at least one stone is left in the same row or column.
24function removeStones(stones: Point[]): number {
25    // Define a large enough value for the maximum coordinate.
26    const maxCoord = 10010;
27    // Initialize the 'parents' collection to twice the value of 'maxCoord'.
28    initParents(maxCoord << 1);
29
30    // Perform union operations for the stones.
31    stones.forEach(([row, col]) => {
32        const rowParent = find(row);
33        const colParent = find(col + maxCoord);
34        parents[rowParent] = colParent;
35    });
36
37    // Using a set to store unique roots after path compression,
38    // which indicates the connected components.
39    const uniqueRoots = new Set<number>();
40    stones.forEach(([row, _]) => {
41        uniqueRoots.add(find(row));
42    });
43
44    // The number of stones that can be removed is the total number of stones
45    // minus the number of unique roots in the disjoint-set forest.
46    return stones.length - uniqueRoots.size;
47}
48

Time and Space Complexity

The given code snippet uses the Union-Find algorithm to remove as many stones as possible on a 2D grid while ensuring at least one stone is left in a connected group (a group of stones connected by either the same row or the same column). The time and space complexity analysis of this code is as follows:

Time Complexity:

  1. The find function is at most traversing the depth of the union-find tree, which, with path compression, results in nearly constant time per operation. However, worst-case without any optimizations can be O(n), but realistically, with path compression, it is closer to O(α(n)), where α(n) is the Inverse Ackermann function, which grows very slowly and is practically considered constant time.
  2. There is a loop that runs once for each stone, and inside this loop, two find operations are performed, one for the x-coordinate and one for the y-coordinate shifted by n to keep the x and y coordinates distinct in the union-find structure.

Considering there are m stones, each union-find operation is O(α(n)), the overall time complexity across all stones will be O(m * α(n)).

Since the Inverse Ackermann function α(n) is practically constant for all reasonable values of n, the time complexity simplifies to O(m).

Space Complexity:

  1. An array p of size n << 1 (or 2 * n) is created to represent the union-find structure, where n is a constant representing the maximum number of different row/column values to expect, set to 10010 in the code. Hence, the space used by p is O(n).
  2. A set s is created to store unique roots after path compression. In the worst case, this set will contain all the stones if none share the same row or column, hence an O(m) space complexity at worst.

Combining these, the total space complexity is O(n + m) which, given the constant size of n, simplifies to O(m), where m is the number of stones.

In summary:

  • Time Complexity: O(m), where m is the number of stones.
  • Space Complexity: O(m), where m is the number of stones.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of these pictures shows the visit order of a depth-first search?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More