O(MN) C++ solution


  • 0
    J
    class Solution {
    public:
        int minTotalDistance(vector<vector<int>>& grid) {
            if(grid.size()==0 || grid[0].size()==0)
            {
                return 0;
            }
            
            vector<int> x,y;
            for(int i=0;i<grid.size();i++)
            {
                for(int j=0;j<grid[0].size();j++)
                {
                    if(grid[i][j]==1)
                    {
                        x.push_back(i);
                    }
                }
            }
            
            for(int j=0;j<grid[0].size();j++)
            {
                for(int i=0;i<grid.size();i++)
                {
                    if(grid[i][j]==1)
                    {
                        y.push_back(j);
                    }
                }
            }
            
            int ret = 0;
            for(int i=0;i<x.size()/2;i++)
            {
                ret += x[x.size()-1-i] - x[i];
                ret += y[y.size()-1-i] - y[i];
            }
            
            return ret;
        }
    };

Log in to reply
 

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