\/**<\/p>\n\n\n\n
* 947. Most Stones Removed with Same Row or Column<\/p>\n\n\n\n
\u00a0* On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.<\/p>\n\n\n\n
\u00a0* A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.<\/p>\n\n\n\n
* Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone,<\/p>\n\n\n\n
\u00a0* return the largest possible number of stones that can be removed.<\/p>\n\n\n\n
\u00a0* Example 1:<\/p>\n\n\n\n
* Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]<\/p>\n\n\n\n
* Output: 5<\/p>\n\n\n\n
* Explanation: One way to remove 5 stones is as follows:<\/p>\n\n\n\n
* 1. Remove stone [2,2] because it shares the same row as [2,1].<\/p>\n\n\n\n
* 2. Remove stone [2,1] because it shares the same column as [0,1].<\/p>\n\n\n\n
* 3. Remove stone [1,2] because it shares the same row as [1,0].<\/p>\n\n\n\n
* 4. Remove stone [1,0] because it shares the same column as [0,0].<\/p>\n\n\n\n
* 5. Remove stone [0,1] because it shares the same row as [0,0].<\/p>\n\n\n\n
* Stone [0,0] cannot be removed since it does not share a row\/column with another stone still on the plane.<\/p>\n\n\n\n
\u00a0* Example 2:<\/p>\n\n\n\n
* Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]<\/p>\n\n\n\n
* Output: 3<\/p>\n\n\n\n
* Explanation: One way to make 3 moves is as follows:<\/p>\n\n\n\n
* 1. Remove stone [2,2] because it shares the same row as [2,0].<\/p>\n\n\n\n
* 2. Remove stone [2,0] because it shares the same column as [0,0].<\/p>\n\n\n\n
* 3. Remove stone [0,2] because it shares the same row as [0,0].<\/p>\n\n\n\n
* Stones [0,0] and [1,1] cannot be removed since they do not share a row\/column with another stone still on the plane.<\/p>\n\n\n\n
\u00a0* Example 3:<\/p>\n\n\n\n
* Input: stones = [[0,0]]<\/p>\n\n\n\n
* Output: 0<\/p>\n\n\n\n
* Explanation: [0,0] is the only stone on the plane, so you cannot remove it.<\/p>\n\n\n\n
* \/<\/p>\n\n\n\n
See the solution on github here:<\/p>\n\n\n\n
https:\/\/github.com\/zcoderz\/leetcode\/blob\/main\/src\/main\/java\/graph\/StonesRemoved.java<\/a><\/p>\n\n\n\n The solution will use union find (disjoint sets) to solve the problem. See the union find algorithm on wiki pedia here: https:\/\/en.wikipedia.org\/wiki\/Disjoint-set_data_structure<\/a><\/p>\n\n\n\n See my code on union find at github here: https:\/\/github.com\/zcoderz\/leetcode\/blob\/main\/src\/main\/java\/utils\/graph\/generic\/UnionFindNode.java<\/a><\/p>\n\n\n\n The algorithm is:<\/p>\n\n\n\n \/** * 947. Most Stones Removed with Same Row or Column \u00a0* On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone. \u00a0* A stone can be removed if it shares either the same row or the same column as another stone thatContinue reading “947. Most Stones Removed With Same Row Or Column”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"wf_page_folders":[21],"class_list":["post-430","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/pages\/430","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/uqcodewall.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=430"}],"version-history":[{"count":5,"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/pages\/430\/revisions"}],"predecessor-version":[{"id":1609,"href":"https:\/\/uqcodewall.com\/index.php?rest_route=\/wp\/v2\/pages\/430\/revisions\/1609"}],"wp:attachment":[{"href":"https:\/\/uqcodewall.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=430"}],"wp:term":[{"taxonomy":"wf_page_folders","embeddable":true,"href":"https:\/\/uqcodewall.com\/index.php?rest_route=%2Fwp%2Fv2%2Fwf_page_folders&post=430"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Here is the code:<\/h4>\n\n\n
\npublic int removeStones(int[][] stones) {\n Map<Integer, UnionFindNode<Integer>> unionFindMap = new HashMap<>();\n for (int i = 0; i < stones.length; i++) {\n UnionFindNode<Integer> unionA = new UnionFindNode<>(stones[i][0]);\n \/\/adding 20000 to cols , so columns and rows have diff ids\n UnionFindNode<Integer> unionB = new UnionFindNode<>(stones[i][1] + 20000);\n unionFindMap.put(stones[i][0], unionA);\n unionFindMap.put(stones[i][1] + 20000, unionB);\n unionA.union(unionB);\n }\n Set<Integer> parentsSet = new HashSet<>();\n for (int i = 0; i < stones.length; i++) {\n UnionFindNode<Integer> unionA = unionFindMap.get(stones[i][0]);\n parentsSet.add(unionA.find().getValue());\n }\n return stones.length - parentsSet.size();\n}\n<\/pre><\/div>","protected":false},"excerpt":{"rendered":"