Accepted C++ solution


  • 3
    J
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<int> row;
        vector<int> col;
        
        for(int i = 0; i<grid.size(); i++) {
            for(int j = 0; j<grid[i].size(); j++) {
                if(grid[i][j] == 1) {
                    row.push_back(i);
                    col.push_back(j);
                }
            }
        }
    
        sort(row.begin(), row.end());
        sort(col.begin(), col.end());
        
        int mid_row = row.size()%2? row[row.size()/2]: (row[row.size()/2 - 1] + row[row.size()/2]) / 2;
        int mid_col = col.size()%2? col[col.size()/2]: (col[col.size()/2 - 1] + col[col.size()/2]) / 2;
        
        int dist = 0;
        for(int i = 0; i<row.size(); i++) 
            dist += abs(mid_row - row[i]);
        for(int i = 0; i<col.size(); i++) 
            dist += abs(mid_col - col[i]);
    
        return dist;
    }

  • 0
    Z

    Why do we need
    sort(row.begin(), row.end());


  • 0
    J

    The key to solve this problem is finding median values. We need to sort the vectors because the input is not sorted.


  • 0
    Z

    Right. But I think the row vector has been sorted when you add elements to it, while the col vector indeed needs to be sorted. Since you iterate the grid from the top to the bottom.


  • 0
    J

    Oh, I got your point. Yes. We don't need to sort the row vector. Thank you for your comment!!


Log in to reply
 

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