Best Meeting Point

Easy
0/40
Average time to solve is 15m
14 upvotes
Asked in companies
HCL TechnologiesAmdocs

Problem statement

Ninja, along with his family, moved to a new city, and Ninja has no friends. He started making new friends from his school. Now he has a number of friends. His friends decided to meet in the evening, but all are confused about where to meet?

Ninja is very busy doing some other works. Can you help Ninja find a place where Ninja and all his friends can meet such that the sum of distance traveled by Ninja and his friends is the minimum possible? Find the place and print the total sum of distances traveled by Ninja and his friends.

You are given the location of Ninja and his friends in the form of a matrix. In the matrix, wherever the value is 1, it means that there is a home at that point (Ninja’s home or the home of some of his friends). Ninja and his friends can meet at any possible coordinate in the matrix, not necessarily at the home of any of the friends.

Manhattan distance is used to calculate the distance between two points, i.e, distance(a, b) = |a.x - b.x| + |a.y - b.y|, (where a.x is the x coordinate of point ‘a’, a.y is the y coordinate of point ‘a’, b.x is the x coordinate of point ‘b’, b.y is the y coordinate of point ‘b’ respectively).

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line contains two space-separated integers, ‘N’ and ‘M’, which denotes the number of rows and columns in the matrix ‘MAT’.

Each of the next ‘N’ lines contains ‘M’ space-separated integers denoting the 'N' tows of the matrix 'MAT'
Output Format: 
For each test case, print a single line containing a single integer denoting the minimum total distance traveled by you and your friends.

The output of each test case will be printed in a separate line.
Note: 
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 500
1 <= M <= 500
0 <= MAT[i][j] <= 1

Where 'T' is the number of test cases, N, M denotes the number of rows and columns in the matrix ‘MAT’, and MAT[i][j] denotes the element present at the i'th row and the j'th column of the matrix 'MAT'.  

Time Limit: 1 sec.
Sample Input 1:
2
3 3
1 0 0
0 0 0
0 0 1
3 3
1 1 0
0 1 0
0 1 1
Sample Output 1:
4
6
Explanation for Sample Input 1:
In the first test case, there are two friends, including Ninja, with homes at (0, 0), and (2, 2). The minimum sum of distance which both have to travel is 4, and one of the meeting points is (0, 0). There are also other meeting points that have total distance traveled equal to 4 - (0, 2), (2, 0), (2, 2). You can choose any of the points to satisfy the given conditions.

In the second test case, there are six friends, including Ninja, with homes at (0, 0), (0, 1), (1, 1), (2, 1), and (2, 2). The minimum sum of distance which all have to travel is 6, and the meeting point is (1, 1). There is only one meeting point that has the sum of distances equal to 6.
Sample Input 2:
2
5 5
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
4 3
1 0 1
1 1 0
0 0 0
1 0 0
Sample Output 2:
32
7
Hint

Can you iterate over all the points and find the total distance traveled by all the friends?

Approaches (2)
Brute Force

The idea is to iterate over all the points and find what is the total distance traveled by all the friends if the current point is being chosen as a meeting point and select the point which gives the minimum possible distance as the meeting point.

 

The steps are as follows:

  • Initialize an integer minDistanceTravelled to 0, which stores the minimum distance traveled from the home of all the friends to the meeting point.
  • Iterate from a = 0 to N-1:
    • Iterate from b = 0 to M-1:
      • Initialize currentDistance to 0, which stores the distance traveled by Ninjas and all his friends when (a, b) is chosen as the meeting point.
      • Iterate from i = 0 to N-1:
        • Iterate from j = 0 to M - 1:
          • If the current element, i.e., MAT[i][j] is equal to 1, then add the distance from the meeting point to the current point in currentDistance, i.e., abs(a-i) + abs(b-j).
      • Update minDistanceTravelled to the minimum of minDistanceTravelled and currentDistance.
  • Return minDistanceTravelled as the final answer.
Time Complexity

O((N * M) ^ 2), where N is the number of rows and M is the number of columns in the matrix ‘MAT’.

 

As we are traversing through all the N * M points and for each point we consider it as the meeting point and then we are traversing through all N * M points to find the sum of distances from the meeting point to the homes of all the friends. Hence, the overall time complexity is O((N * M) ^ 2).

Space Complexity

O(1).

 

As we are using constant extra space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Best Meeting Point
Full screen
Console