Most Stones Removed with Same Row or Column

TIP103 Unit 7 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-35 mins
• 🛠️ Topics: Graphs, Union-Find (Disjoint Set), Connected Components

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: When can a stone be removed?

  • A: A stone can be removed if at least one other stone that has not yet been removed shares its row or its column.

• Q: Does the order in which we remove stones matter?

  • A: The order matters for how we remove them, but not for the maximum count. Within any group of stones connected through shared rows/columns, we can always remove stones from the outside in until exactly one stone remains. So the answer is total stones - number of connected groups.

• Q: Can two stones occupy the same coordinate?

  • A: No, each stone is at a unique coordinate point.

HAPPY CASE
Input: stones = [[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]
Output: 5
Explanation: All 6 stones are connected through shared rows and columns, forming one group. We can remove all but one stone, so 6 - 1 = 5 stones can be removed.

Input: stones = [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]
Output: 3
Explanation: The four corner stones [0,0], [0,2], [2,0], [2,2] share rows 0/2 and columns 0/2, forming one connected group. The center stone [1,1] shares no row or column with any other stone, forming a second group. With 5 stones in 2 groups, we can remove 5 - 2 = 3 stones.

EDGE CASE
Input: stones = [[0, 0]]
Output: 0
Explanation: A single stone shares no row or column with another stone, so it can never be removed.

Input: stones = [[0, 0], [1, 1], [2, 2]]
Output: 0
Explanation: No two stones share a row or column, so every stone is its own group and none can be removed.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Connected Components Problems, we can consider the following approaches:

• Union-Find (Disjoint Set): Group stones into connected components by unioning each stone's row with its column. The answer is the total number of stones minus the number of components.
• DFS (Depth-First Search): Build a graph where stones sharing a row or column are neighbors, then count connected components with DFS.

The key insight is a reduction: within any connected group of k stones, we can always remove k - 1 of them (remove leaves of a spanning tree first, working inward). So the problem reduces to counting connected components.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Instead of connecting stones to stones (which requires comparing every pair), connect each stone's row to its column in a Union-Find structure. Two stones that share a row or column will then automatically end up in the same set. The answer is len(stones) - number of distinct components.

To keep row identifiers from colliding with column identifiers (row 1 and column 1 are different graph nodes), tag them differently, e.g. ("row", r) and ("col", c).

1) Initialize a Union-Find structure with `find` (with path compression) and `union` operations.
2) For each stone at (row, col):
   a) Create nodes ("row", row) and ("col", col) if they don't exist yet.
   b) Union the row node with the column node.
3) Count the number of distinct components by collecting find(("row", row)) for every stone into a set.
4) Return len(stones) - number of distinct components.

⚠️ Common Mistakes

• Treating row i and column i as the same node — they must be kept distinct (offset or tag one of them), or unrelated stones get merged.
• Trying to simulate the removal process stone by stone instead of recognizing the connected-components reduction.
• Comparing every pair of stones to build the graph, which is O(N^2); unioning rows with columns avoids this.
• Returning the number of components instead of len(stones) - components.

4: I-mplement

Implement the code to solve the algorithm.

def remove_stones(stones):
    parent = {}

    def find(x):
        # Follow parent pointers to the root, compressing the path as we go
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x != root_y:
            parent[root_x] = root_y

    # Union each stone's row node with its column node.
    # Tag rows and columns differently so row i and column i stay distinct.
    for row, col in stones:
        row_node = ("row", row)
        col_node = ("col", col)
        parent.setdefault(row_node, row_node)
        parent.setdefault(col_node, col_node)
        union(row_node, col_node)

    # Count distinct connected components among the stones
    components = {find(("row", row)) for row, col in stones}
    return len(stones) - len(components)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: stones = 0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2

  • Stone [0,0] unions row 0 with col 0; [0,1] unions row 0 with col 1; [1,0] unions row 1 with col 0; [1,2] unions row 1 with col 2; [2,1] unions row 2 with col 1; [2,2] unions row 2 with col 2.
  • Every row and column node ends up in one set, so all 6 stones form 1 component.
  • Output: 6 - 1 = 5

• Input: stones = 0, 0], [0, 2], [1, 1], [2, 0], [2, 2

  • Rows 0 and 2 and columns 0 and 2 all merge into one set through the four corner stones (1 component of 4 stones).
  • Stone [1,1] unions row 1 with col 1, which touch no other stone (a 2nd component).
  • Output: 5 - 2 = 3

• Input: stones = 0, 0

  • One stone, one component.
  • Output: 1 - 1 = 0

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of stones.

• Time Complexity: O(N * α(N)), effectively O(N), where α is the inverse Ackermann function — we perform one union per stone and one find per stone, each nearly constant time with path compression.
• Space Complexity: O(N) for the parent dictionary, which holds at most 2N row and column nodes.