{"id":"ef60ab6b-0117-45b9-84e9-93b3ff20c0c3","name":"Kill The Most Monsters","description":"On a 2D plane, we place n monsters at some integer coordinate points. Each coordinate point may have at most one monster.\r\n\r\nA monster can be removed if it shares either the same row or the same column as another monster that has not been removed.\r\n\r\nGiven an array monsters of length n where monsters[i] = [xi, yi] represents the location of the ith monster, return the largest possible number of monsters that can be removed.\r\n\r\nExample 1:\r\n\r\n Input: monsters = [[0,0],[0,2],[1,1],[2,0],[2,2]]\r\n Output: 3\r\n\r\nExplanation: One way to make 3 moves is as follows:\r\n1. Remove monster [2,2] because it shares the same row as [2,0].\r\n2. Remove monster [2,0] because it shares the same column as [0,0].\r\n3. Remove monster [0,2] because it shares the same row as [0,0].\r\nmonsters [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.","inputFormat":"Input/output is handled for you. You just need to complete the function.","outputFormat":"Input/output is handled for you. You just need to complete the function.","constraints":"\r\n1. 1 &lt;= monsters.length &lt;= 1000\r\n2. 0 &lt;= monsters[i][0],monsters[i][1] &lt;= 1","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n public static int removeMonsters(int[][] monsters) {\r\n // Write your code here\r\n }\r\n\r\n public static void main(String[] args) {\r\n\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n\r\n int[][] monsters = new int[n][2];\r\n for (int i = 0; i < n; i++) {\r\n monsters[i][0] = scn.nextInt();\r\n monsters[i][1] = scn.nextInt();\r\n }\r\n\r\n int ans = removeMonsters(monsters);\r\n System.out.println(ans);\r\n }\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"6\r\n0\r\n0\r\n0\r\n1\r\n1\r\n0\r\n1\r\n2\r\n2\r\n1\r\n2\r\n2","sampleOutput":"5\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"fbbc02b5-cdb2-48af-9872-49cb06034328","name":"Kill The Most Monsters","slug":"kill-the-most-monsters","type":1}],"next":{"id":"70e442d0-424b-466c-a9d6-77203298e3bc","name":"Kill the Most Monsters","type":0,"slug":"kill-the-most-monsters"},"prev":{"id":"d0ba362a-5eb5-4287-a5fe-6565876b91d8","name":"SLIDING PUZZLE","type":3,"slug":"sliding-puzzle"}}}

Kill The Most Monsters

On a 2D plane, we place n monsters at some integer coordinate points. Each coordinate point may have at most one monster. A monster can be removed if it shares either the same row or the same column as another monster that has not been removed. Given an array monsters of length n where monsters[i] = [xi, yi] represents the location of the ith monster, return the largest possible number of monsters that can be removed. Example 1: Input: monsters = [[0,0],[0,2],[1,1],[2,0],[2,2]] Output: 3 Explanation: One way to make 3 moves is as follows: 1. Remove monster [2,2] because it shares the same row as [2,0]. 2. Remove monster [2,0] because it shares the same column as [0,0]. 3. Remove monster [0,2] because it shares the same row as [0,0]. monsters [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.

{"id":"ef60ab6b-0117-45b9-84e9-93b3ff20c0c3","name":"Kill The Most Monsters","description":"On a 2D plane, we place n monsters at some integer coordinate points. Each coordinate point may have at most one monster.\r\n\r\nA monster can be removed if it shares either the same row or the same column as another monster that has not been removed.\r\n\r\nGiven an array monsters of length n where monsters[i] = [xi, yi] represents the location of the ith monster, return the largest possible number of monsters that can be removed.\r\n\r\nExample 1:\r\n\r\n Input: monsters = [[0,0],[0,2],[1,1],[2,0],[2,2]]\r\n Output: 3\r\n\r\nExplanation: One way to make 3 moves is as follows:\r\n1. Remove monster [2,2] because it shares the same row as [2,0].\r\n2. Remove monster [2,0] because it shares the same column as [0,0].\r\n3. Remove monster [0,2] because it shares the same row as [0,0].\r\nmonsters [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.","inputFormat":"Input/output is handled for you. You just need to complete the function.","outputFormat":"Input/output is handled for you. You just need to complete the function.","constraints":"\r\n1. 1 &lt;= monsters.length &lt;= 1000\r\n2. 0 &lt;= monsters[i][0],monsters[i][1] &lt;= 1","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n public static int removeMonsters(int[][] monsters) {\r\n // Write your code here\r\n }\r\n\r\n public static void main(String[] args) {\r\n\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n\r\n int[][] monsters = new int[n][2];\r\n for (int i = 0; i < n; i++) {\r\n monsters[i][0] = scn.nextInt();\r\n monsters[i][1] = scn.nextInt();\r\n }\r\n\r\n int ans = removeMonsters(monsters);\r\n System.out.println(ans);\r\n }\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"6\r\n0\r\n0\r\n0\r\n1\r\n1\r\n0\r\n1\r\n2\r\n2\r\n1\r\n2\r\n2","sampleOutput":"5\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"fbbc02b5-cdb2-48af-9872-49cb06034328","name":"Kill The Most Monsters","slug":"kill-the-most-monsters","type":1}],"next":{"id":"70e442d0-424b-466c-a9d6-77203298e3bc","name":"Kill the Most Monsters","type":0,"slug":"kill-the-most-monsters"},"prev":{"id":"d0ba362a-5eb5-4287-a5fe-6565876b91d8","name":"SLIDING PUZZLE","type":3,"slug":"sliding-puzzle"}}}
plane

Editor


Loading...

Kill The Most Monsters

easy

On a 2D plane, we place n monsters at some integer coordinate points. Each coordinate point may have at most one monster. A monster can be removed if it shares either the same row or the same column as another monster that has not been removed. Given an array monsters of length n where monsters[i] = [xi, yi] represents the location of the ith monster, return the largest possible number of monsters that can be removed. Example 1: Input: monsters = [[0,0],[0,2],[1,1],[2,0],[2,2]] Output: 3 Explanation: One way to make 3 moves is as follows: 1. Remove monster [2,2] because it shares the same row as [2,0]. 2. Remove monster [2,0] because it shares the same column as [0,0]. 3. Remove monster [0,2] because it shares the same row as [0,0]. monsters [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.

Constraints

1. 1 <= monsters.length <= 1000 2. 0 <= monsters[i][0],monsters[i][1] <= 1

Format

Input

Input/output is handled for you. You just need to complete the function.

Output

Input/output is handled for you. You just need to complete the function.

Example

Sample Input

6 0 0 0 1 1 0 1 2 2 1 2 2

Sample Output

5

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode