{"id":"ca85a2b3-9b97-43ba-977d-f8938097b7fb","name":"Best Meeting Point","description":"1. A group of two or more people wants to meet and minimize the total travel distance.\r\n2. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. \r\n3. Return min distance where distance is calculated using 'Manhattan Distance', where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.\r\n","inputFormat":"[\r\n [1,0,0,0,1],\r\n [0,0,0,0,0],\r\n [0,0,1,0,0]\r\n]","outputFormat":"6\r\n\r\nExplanation:\r\nThe point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal. So return 6.","constraints":"1 &lt;= grid.length &lt;= 10^4\r 1 &lt;= grid[i].length \t&lt;= 10^4","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\nint main(){\n    //write your code here..\n}"},"java":{"code":"import java.util.*;\npublic class Main\n{\n    public static void main(String[] args) {\n        //write your code here..\n    }\n}"},"python":{"code":"def main():\n\n    #write your code here..\n\nif __name__==\"__main__\":\n\n    main()"}},"points":10,"difficulty":"easy","sampleInput":"3 5\r\n1 0 0 0 1\r\n0 0 0 0 0\r\n0 0 1 0 0","sampleOutput":"6","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":"35f2cfb0-6f25-4967-b0c9-92f2384b9260","name":"Arrays And Strings For Intermediate","slug":"arrays-and-strings-for-intermediate-732","type":0},{"id":"b55c4642-19c6-4a78-a894-8c2a9905166e","name":"Best Meeting Point","slug":"best-meeting-point","type":1}],"next":{"id":"399a904a-66a0-4e37-ae1c-de960f86b6fb","name":"Best Meeting Point","type":3,"slug":"best-meeting-point"},"prev":{"id":"cf366cb9-2f34-4d4c-8873-58c9b472a637","name":"Reverse Vowels Of A String","type":3,"slug":"reverse-vowels-of-a-string"}}}

Best Meeting Point

1. A group of two or more people wants to meet and minimize the total travel distance. 2. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. 3. Return min distance where distance is calculated using 'Manhattan Distance', where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

{"id":"ca85a2b3-9b97-43ba-977d-f8938097b7fb","name":"Best Meeting Point","description":"1. A group of two or more people wants to meet and minimize the total travel distance.\r\n2. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. \r\n3. Return min distance where distance is calculated using 'Manhattan Distance', where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.\r\n","inputFormat":"[\r\n [1,0,0,0,1],\r\n [0,0,0,0,0],\r\n [0,0,1,0,0]\r\n]","outputFormat":"6\r\n\r\nExplanation:\r\nThe point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal. So return 6.","constraints":"1 &lt;= grid.length &lt;= 10^4\r 1 &lt;= grid[i].length \t&lt;= 10^4","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\nint main(){\n    //write your code here..\n}"},"java":{"code":"import java.util.*;\npublic class Main\n{\n    public static void main(String[] args) {\n        //write your code here..\n    }\n}"},"python":{"code":"def main():\n\n    #write your code here..\n\nif __name__==\"__main__\":\n\n    main()"}},"points":10,"difficulty":"easy","sampleInput":"3 5\r\n1 0 0 0 1\r\n0 0 0 0 0\r\n0 0 1 0 0","sampleOutput":"6","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":"35f2cfb0-6f25-4967-b0c9-92f2384b9260","name":"Arrays And Strings For Intermediate","slug":"arrays-and-strings-for-intermediate-732","type":0},{"id":"b55c4642-19c6-4a78-a894-8c2a9905166e","name":"Best Meeting Point","slug":"best-meeting-point","type":1}],"next":{"id":"399a904a-66a0-4e37-ae1c-de960f86b6fb","name":"Best Meeting Point","type":3,"slug":"best-meeting-point"},"prev":{"id":"cf366cb9-2f34-4d4c-8873-58c9b472a637","name":"Reverse Vowels Of A String","type":3,"slug":"reverse-vowels-of-a-string"}}}
plane

Editor

Loading...

Best Meeting Point

easy

1. A group of two or more people wants to meet and minimize the total travel distance. 2. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. 3. Return min distance where distance is calculated using 'Manhattan Distance', where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Constraints

1 <= grid.length <= 10^4 1 <= grid[i].length <= 10^4

Format

Input

[ [1,0,0,0,1], [0,0,0,0,0], [0,0,1,0,0] ]

Output

6 Explanation: The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal. So return 6.

Example

Sample Input

3 5 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0

Sample Output

6

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode