C++ O(N) Space O(N) Time, 12-line Short and Clean Solution


  • 1
    F

    To clarify, here N is the size of matrix

    struct Solution {
        int minTotalDistance(vector<vector<int>>& grid) {
            if (grid.empty()) return 0;
            vector<int> vec_i, vec_j;
            for (int i = 0; i < grid.size(); ++ i)
                for (int j = 0; j < grid[0].size(); ++ j)
                    if (grid[i][j] == 1) 
                        vec_i.push_back(i), vec_j.push_back(j);
            nth_element(vec_i.begin(), vec_i.begin() + vec_i.size()/2, vec_i.end());
            nth_element(vec_j.begin(), vec_j.begin() + vec_j.size()/2, vec_j.end());
            int dist = 0, mid_i = vec_i[vec_i.size()/2], mid_j = vec_j[vec_j.size()/2];
            for (int k = 0; k < vec_i.size(); ++k)
                dist += abs(vec_i[k] - mid_i) + abs(vec_j[k] - mid_j);
            return dist;
        }
    };

Log in to reply
 

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