Share my O(M*N) solution


  • 0
    L
    public class Solution
    {
        public int MinTotalDistance(int[,] grid)
        {
    
            int rows = grid.GetLength(0);
            int cols = grid.GetLength(1);
    
            int[,] points = new int[rows, cols];
    
            int[] rowsMapping = new int[rows];
    
            int[] colsMapping = new int[cols];
    
            int totalResult = 0;
    
            for (int i = 0; i < rows; i++)
            {
                int sum = 0;
                for (int j = 0; j < cols; j++)
                {
                    if (grid[i, j] == 1)
                    {
                        sum++;
                        totalResult++;
                        points[0, 0] += (i + j);
                    }
                    colsMapping[j] += sum;
                }
                rowsMapping[i] = totalResult;
            }
    
            int result = points[0, 0];
    
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < cols; j++)
                {
                    if (i == 0 && j == 0)
                        continue;
                    if (j == 0)
                        points[i, j] = points[i - 1, j] + rowsMapping[i-1] - (totalResult - rowsMapping[i-1]);
                    else
                        points[i, j] = points[i, j - 1] + colsMapping[j-1] - (totalResult - colsMapping[j-1]);
    
                    result = Math.Min(result, points[i, j]);
                }
            }
    
            return result;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.