Most Stones Removed with Same Row or Column

📋

Most Stones Removed with Same Row or Column

Edge cases:

</>

IDE

def removeStones(stones: list[list[int]]) -> int:public int removeStones(int[][] stones)int removeStones(vector<vector<int>>& stones)function removeStones(stones)

def removeStones(stones):
    # Write your solution here
    pass

class Solution {
    public int removeStones(int[][] stones) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int removeStones(vector<vector<int>>& stones) {
    // Write your solution here
    return 0;
}

function removeStones(stones) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Incorrectly counting each stone as isolated component; union-find merges missing.✅ Union stones sharing same row or column before counting components.

Wrong: nAlways returning total stones without subtracting connected components.✅ Return total stones minus number of connected components.

Wrong: TLEUsing O(n^2) pairwise comparisons for large inputs.✅ Use union-find with path compression and map rows and columns to indices to avoid pairwise checks.

Wrong: Incorrect count when duplicates presentNot handling stones with identical coordinates as one component.✅ Union stones with identical coordinates properly.

Wrong: Incorrect count when no stones share row or columnMerging stones incorrectly without checking row or column equality.✅ Only union stones if they share the same row or the same column.

✓

Test Cases

Focus on handling edge cases like empty input and single stones correctly.

Test your code against tricky cases where stones do not share rows or columns.

Optimize your union-find implementation to handle large inputs efficiently.

t1_01basic

Input{"stones":[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]}

Expected5

⏱ Performance - must finish in 2000ms

One way to remove 5 stones is to remove stones in the order: [2,2], [2,1], [1,2], [1,0], [0,1]. The stone at [0,0] remains.

💡 Think of stones as nodes connected if they share a row or column.

💡 Use union-find or DFS to find connected components and count them.

💡 The answer is total stones minus number of connected components.

Why it failed: Incorrect output means union-find or DFS logic is wrong; ensure you count connected components correctly and subtract from total stones.

✓ Correctly identified connected components and computed maximum stones removable.

t1_02basic

Input{"stones":[[0,0],[0,2],[1,1],[2,0],[2,2]]}

Expected3

⏱ Performance - must finish in 2000ms

There are 2 connected components: one with stones at [0,0],[0,2],[2,0],[2,2] and one isolated stone at [1,1]. Max stones removed = 5 - 2 = 3.

💡 Group stones by rows and columns to find connected components.

💡 Check if stones share row or column to union them.

💡 Subtract number of connected components from total stones for answer.

Why it failed: If output is not 3, likely union-find merges are incorrect; verify union conditions and component counting.

✓ Correctly handled multiple connected components and computed removable stones.

t2_01edge

Input{"stones":[]}

Expected0

⏱ Performance - must finish in 2000ms

No stones means no stones can be removed.

💡 Check how your code handles empty input.

💡 Ensure no indexing or union-find operations occur on empty arrays.

💡 Return 0 immediately if stones list is empty.

Why it failed: Code crashes or returns non-zero on empty input; add guard clause for empty stones array.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"stones":[[5,5]]}

Expected0

⏱ Performance - must finish in 2000ms

Only one stone means no other stone shares row or column; cannot remove any stone.

💡 Single stone forms one connected component.

💡 Max stones removed = total stones - number of components = 1 - 1 = 0.

💡 Check that your code handles single-element input correctly.

Why it failed: If output is not 0, code likely miscounts components or removes stones incorrectly for single stone input.

✓ Correctly returns 0 for single stone input.

t2_03edge

Input{"stones":[[1,0],[1,1],[1,2],[1,3]]}

Expected3

⏱ Performance - must finish in 2000ms

All stones share the same row, so they form one connected component; max stones removed = 4 - 1 = 3.

💡 All stones in same row form a single connected component.

💡 Union all stones with same row index.

💡 Result is total stones minus one.

Why it failed: If output is not 3, union by row is not implemented correctly; fix union condition to merge stones sharing rows.

✓ Correctly handles all stones in same row.

t2_04edge

Input{"stones":[[0,2],[1,2],[2,2],[3,2]]}

Expected3

⏱ Performance - must finish in 2000ms

All stones share the same column, so they form one connected component; max stones removed = 4 - 1 = 3.

💡 All stones in same column form a single connected component.

💡 Union all stones with same column index.

💡 Result is total stones minus one.

Why it failed: If output is not 3, union by column is not implemented correctly; fix union condition to merge stones sharing columns.

✓ Correctly handles all stones in same column.

t3_01corner

Input{"stones":[[0,0],[1,1],[2,2],[3,3]]}

Expected0

⏱ Performance - must finish in 2000ms

No two stones share the same row or column; each stone is isolated; max stones removed = 4 - 4 = 0.

💡 Check if your union-find merges stones only when rows or columns match exactly.

💡 Avoid merging stones that do not share row or column.

💡 Ensure counting connected components correctly when no merges happen.

Why it failed: If output > 0, code incorrectly merges stones without shared row/column; fix union condition to only merge stones sharing row or column.

✓ Correctly identifies isolated stones and returns 0.

t3_02corner

Input{"stones":[[0,0],[0,1],[1,0],[1,1],[2,2]]}

Expected4

⏱ Performance - must finish in 2000ms

Four stones form one connected component (0,0),(0,1),(1,0),(1,1); stone (2,2) isolated; max stones removed = 5 - 2 = 3.

💡 Check if your code merges stones sharing row or column correctly.

💡 Verify that isolated stones form separate components.

💡 Count components accurately to compute removable stones.

Why it failed: If output is 3 instead of 4, code may be miscounting components or incorrectly merging isolated stones; fix union-find logic.

✓ Correctly handles mixed connected and isolated stones.

t3_03corner

Input{"stones":[[0,0],[0,0],[0,0]]}

Expected2

⏱ Performance - must finish in 2000ms

All stones at same position form one connected component; max stones removed = 3 - 1 = 2.

💡 Handle duplicates correctly; they belong to the same component.

💡 Union-find should merge stones with identical coordinates.

💡 Result is total stones minus one component.

Why it failed: If output is less than 2, code may not handle duplicates correctly; fix union-find to merge stones with identical coordinates.

✓ Correctly handles multiple stones at same position.

t4_01performance

Input{"stones":[[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8],[9,9],[10,0],[11,1],[12,2],[13,3],[14,4],[15,5],[16,6],[17,7],[18,8],[19,9],[20,0],[21,1],[22,2],[23,3],[24,4],[25,5],[26,6],[27,7],[28,8],[29,9],[30,0],[31,1],[32,2],[33,3],[34,4],[35,5],[36,6],[37,7],[38,8],[39,9],[40,0],[41,1],[42,2],[43,3],[44,4],[45,5],[46,6],[47,7],[48,8],[49,9],[50,0],[51,1],[52,2],[53,3],[54,4],[55,5],[56,6],[57,7],[58,8],[59,9],[60,0],[61,1],[62,2],[63,3],[64,4],[65,5],[66,6],[67,7],[68,8],[69,9],[70,0],[71,1],[72,2],[73,3],[74,4],[75,5],[76,6],[77,7],[78,8],[79,9],[80,0],[81,1],[82,2],[83,3],[84,4],[85,5],[86,6],[87,7],[88,8],[89,9],[90,0],[91,1],[92,2],[93,3],[94,4],[95,5],[96,6],[97,7],[98,8],[99,9]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 stones with varying rows and columns; solution must run in O(n α(n)) time within 2 seconds.

💡 Use union-find with path compression for efficient merges.

💡 Avoid O(n^2) pairwise comparisons.

💡 Map rows and columns to union-find indices to optimize.

Why it failed: TLE indicates brute force or inefficient union-find; optimize to O(n α(n)) with path compression and union by rank.

✓ Efficient union-find implementation confirmed by passing performance test.

Practice

1. You are given a network of cities represented as an n x n matrix where isConnected[i][j] = 1 means city i is directly connected to city j. Your task is to find how many groups of cities are connected directly or indirectly. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that picks the city with the most connections first

B. Sorting cities by their connection counts and merging groups

C. Graph traversal using DFS or BFS to find connected components

D. Dynamic programming to count paths between cities

Solution

1. Step 1: Understand the problem as finding connected components in a graph

   The problem describes a graph where nodes are cities and edges represent direct connections. The goal is to find how many connected groups exist.

2. Step 2: Identify the algorithm that finds connected components efficiently

   DFS or BFS traversals can explore all nodes reachable from a starting node, marking them visited. Counting how many times you start a new traversal gives the number of connected components.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Connected components are found by graph traversal [OK]

Hint: Connected components -> DFS/BFS traversal [OK]

Common Mistakes:

• Thinking greedy or sorting can find connected components
• Confusing path counting with component counting

2. Given the following code snippet implementing union-find for satisfiability of equality equations, what is the return value of equationsPossible when called with ["a==b", "b!=c", "c==a"]?

easy

A. Depends on input order

B. True

C. Raises an error

D. False

Solution

1. Step 1: Process equalities

   Union 'a' and 'b', then union 'c' and 'a' (via 'c==a'), so 'a', 'b', 'c' are in the same set.

2. Step 2: Check inequalities

   Check 'b!=c': since 'b' and 'c' share the same root, this inequality contradicts the equality sets, so return False.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Contradiction detected correctly [OK]

Hint: Check inequalities after all unions [OK]

Common Mistakes:

• Checking inequalities before unions
• Not path compressing causing wrong roots

3. The following code attempts to implement the optimal solution for the smallest string with swaps problem. Identify the line that contains a subtle bug that can cause incorrect output.

medium

A. Line: for i, idx in enumerate(group): res[idx] = chars[i]

B. Line: groups[uf.find(i)].append(i)

C. Line: for x, y in pairs: uf.union(x, y)

D. Line: chars.sort()

Solution

1. Step 1: Identify grouping and sorting

   Indices in each group are collected but not sorted before assignment.

2. Step 2: Check assignment order

   Assigning sorted characters to unsorted group indices causes characters to be placed incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting group indices before assignment fixes the bug [OK]

Hint: Always sort indices before assigning sorted chars [OK]

Common Mistakes:

• Not sorting indices before assignment
• Assuming group order matches index order

4. What is the time complexity of the optimal union-find approach for the Swim in Rising Water problem on an n x n grid, where n is the grid dimension?

medium

A. O(n^2 log n) due to sorting all n^2 cells and near-constant union-find operations

B. O(n^4) due to nested loops over grid and union operations

C. O(n^2 * maxElevation) because of simulating water rise for each elevation

D. O(n^2) because each cell is processed once with union-find operations

Solution

1. Step 1: Identify main operations

   Sorting all n^2 cells takes O(n^2 log n^2) = O(n^2 log n). Union-find operations are almost O(1) amortized per union/find.

2. Step 2: Combine complexities

   Total complexity dominated by sorting: O(n^2 log n). Union-find merges add negligible overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates; union-find nearly constant time per operation [OK]

Hint: Sorting n^2 cells dominates complexity [OK]

Common Mistakes:

• Assuming union-find operations cost O(log n) each
• Confusing brute force simulation complexity with optimal
• Ignoring sorting cost or treating union-find as O(1) without justification

5. Suppose the problem is modified so that edges can be reused multiple times (i.e., multi-edges allowed), and we want to remove the maximum number of edges while keeping the graph traversable for both Alice and Bob. Which modification to the optimal union-find approach is necessary?

hard

A. Use a multigraph union-find variant that counts edge multiplicities and only removes redundant edges after full connectivity.

B. Switch to a shortest path algorithm since union-find cannot handle multi-edges.

C. No change needed; the original union-find approach works as is.

D. Process edges in arbitrary order without sorting since multi-edges guarantee connectivity.

Solution

1. Step 1: Understand multi-edge impact

   Multi-edges mean multiple edges connect same nodes; union-find alone merges sets once, ignoring multiplicity.

2. Step 2: Modify union-find approach

   Need to track edge counts per connection and only remove edges that do not break connectivity, requiring a multigraph-aware union-find or additional bookkeeping.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Original union-find ignores multiplicity -> must track edge counts [OK]

Hint: Union-find merges sets once; multi-edges require counting edges [OK]

Common Mistakes:

• Assuming union-find handles multi-edges without change
• Ignoring edge multiplicity
• Switching to unrelated algorithms unnecessarily