16ms, easy understandable, C++ solution


  • 4
    I

    It's my first time sharing a solution here. Quite nervous...

    int minTotalDistance(vector<vector<int>>& grid) {
            if(grid.empty()) return 0;
            
            int NumOfRow = grid.size();
            int NumOfCol = grid[0].size();
            vector<int> rows;
            vector<int> cols;
            
            for(int indexOfRow = 0; indexOfRow < NumOfRow; indexOfRow++){
                for(int indexOfCol = 0; indexOfCol < NumOfCol; indexOfCol++){
                    if(grid[indexOfRow][indexOfCol]){
                        rows.push_back(indexOfRow);
                        cols.push_back(indexOfCol);
                    }
                }
            }
            
            // sort(rows.begin(), rows.end()); as this's already sorted 
            sort(cols.begin(), cols.end());
            
            int idealRow = rows[rows.size() / 2];
            int idealCol = cols[cols.size() / 2];
            
            int result = 0;
            
            for(auto row: rows)
                result += abs(row - idealRow);
            for(auto col: cols)
                result += abs(col - idealCol);
    
            return result;
        }

  • 0

    Don't be nervous. Who hasn't 1st time? It's fun :-)


  • 0
    X

    Nice code, very easy to understand!


  • 0
    J

    What if rows.size()%2 = 0? shouldn't we consider int idealRow = rows[rows.size() / 2-1]; also?


  • 0
    A

    Great and clean code. You can use "nth_element(cols.begin(), cols.begin() + cols.size() / 2, cols.end());" instead of "sort(cols.begin(), cols.end());" to make it slightly faster :)


Log in to reply
 

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