LeetCode 296: Best Meeting Point

Explanation:

The problem asks us to find the minimum total distance that all members of a group need to travel to meet at a common point in a 2D grid. The optimal meeting point should be the point that minimizes the total Manhattan distance for all members to that point.

To solve this problem, we can observe that the optimal meeting point will be at the median of the positions in both dimensions. This is because the Manhattan distance is minimized when the meeting point is at the median. We can calculate the Manhattan distance for each member to the median point and sum them up to get the total distance.

Algorithm:

1. Find the median position in both dimensions (rows and columns).
2. Calculate the total distance by iterating through all members and summing up their Manhattan distances to the median point.

Time Complexity:

The time complexity of this algorithm is O(mn) where m is the number of rows and n is the number of columns in the grid.

Space Complexity:

The space complexity of this algorithm is O(1) since we are not using any extra space other than a few variables.

: :

class Solution {
    public int minTotalDistance(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        List<Integer> rows = new ArrayList<>();
        List<Integer> cols = new ArrayList<>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        
        return minDistance(rows) + minDistance(cols);
    }
    
    private int minDistance(List<Integer> points) {
        Collections.sort(points);
        
        int i = 0;
        int j = points.size() - 1;
        int distance = 0;
        
        while (i < j) {
            distance += points.get(j--) - points.get(i++);
        }
        
        return distance;
    }
}