Most Stones Removed with Same Row or Column
MST & Disjoint Set DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Maximum number of stones that can be removed from a 2D plane given specific removal rules (using Disjoint Set Union / Connected Components approach), Disjoint Set Union, Connected Components, Graph, Union by Size, Path Compression, Time Complexity, Space Complexity, Arrays, Hash Map, union-find, graph components, optimization, mapping, graph theory, Disjoint Set Union (DSU) / Union-Find, Binary Matrix Problems, DSU Applications.
Problem Statement There are n stones at some integer coordinate points on a 2D plane. Each coordinate point may have at most one stone. You need to remove some stones. A stone can be removed if it shares either 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 i th stone, return the maximum possible number of stones that you can remove. Example 1: 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] Example 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]