MediumCoding

Most Stones Removed with Same Row or Column

Asked at

Myntra

Amazon

PhonePe

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

There are n stones at integer coordinate points on a 2D plane, with at most one stone per coordinate point. Some stones need to be removed.A stone can be removed if it shares the same row or the same column as another stone that has not been removed.

Given an array of stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the maximum possible number of stones that can be removed.

**Input : **n=6, stones = [[0, 0],[ 0, 1], [1, 0],[1, 2],[2, 1],[2, 2]] Output: 5 Explanation: One of the many ways to remove 5 stones is to remove the following stones: [0,0], [1,0], [0,1], [2,1], [1,2]

Input : n = 6, stones = [[0, 0], [0, 2], [1, 3], [3, 1], [3, 2], [4, 3]] Output: 4 Explanation: We can remove the following stones: [0,0], [0,2], [1,3], [3,1]

**Input: **n = 2, stones = [[0, 0], [0, 2]]

1 <= n <=1000
0 <= x[i], y[i]<= 104
No two stones are at same position.

cpp

class Solution {
public:
    int maxRemove(vector<vector<int>>& stones, int n) {
      
    }
};

java

class Solution {
    public int maxRemove(int[][] stones, int n) {

    }
};

python

class Solution:
    def maxRemove(self, stones, n):

javascript

class Solution {
    maxRemove(stones, n) {
     
    }
}

csharp

public class Solution {
    public int MaxRemove(List<int[]> stones, int n) {
     
    }
}

func maxRemove(stones [][]int, n int) int {
	
}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Connect stones that share a row or column, directly or transitively.
02Use DSU over row nodes and separately offset column nodes.
03Return number of stones minus number of connected components containing stones.
04Count roots only among active row or column nodes.

Reference answer

Within one connected component of stones linked by shared rows or columns, all but one stone can be removed: repeatedly remove a stone while another connected stone remains. One final stone cannot be removed. Therefore the maximum removals are n - numberOfComponents. Build components efficiently with DSU. Represent each row as one node and each column as another namespace, for example column + rowLimit, and union the row and column node for every stone. Track only nodes that actually occur. After all unions, count distinct DSU roots among those active nodes; that is the number of stone components. With path compression and union by size or rank, time is O(n alpha(n)) and space is O(number of active rows and columns). A direct stone-to-stone graph can require O(n squared) comparisons.

Then expect these follow-ups

How would you solve it with DFS instead of DSU?
Tests: alternative graph model
Why can every component remove all but one stone?
Tests: correctness proof

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question