8ms c++ solution, O(n) + O(m) extra space, O(mn) time


  • 1
    S

    Hi,

    The idea is to count the total number of home in each row and column, calculating the distance to each horizontal / vertical point. The point is that the distance can be separately measured for the horizontal and vertical directions, and the optimal point can also be chosen separately.

    class Solution {
    public:
        int minTotalDistance(vector<vector<int>>& grid) {
            if (grid.size() == 0 || grid[0].size() == 0)
                return 0;
            int m = grid.size();
            int n = grid[0].size();
            
            int ver_cnts[m];
            fill_n(ver_cnts, m, 0);
            int c = 0;
    
            // count hor_cnts, ver_cnts
            int hor_cnts[n];
            fill_n(hor_cnts, n, 0);
            for (vector<int> &row: grid)  {
                int ver_cnt = 0;
                for (int i = 0; i < n; i++) {
                    hor_cnts[i] += row[i];
                    ver_cnt += row[i];
                }
                
                ver_cnts[c++] = ver_cnt;
            }
    
            // get the cost to each hor potition
            // hor: the cost of moving horizontally to each column
            int hor[n];
            fill_n(hor, n, 0);
            
            // forward
            int hor_temp[n];
            hor_temp[0] = 0;
            int cnt = hor_cnts[0];
            for (int i = 1; i < n; i++) {
                hor_temp[i] = hor_temp[i-1] + cnt;
                cnt += hor_cnts[i];
            }
            for (int i = 0; i < n; i++) {
                hor[i] += hor_temp[i];
            }
            
            // backward
            hor_temp[n-1] = 0;
            cnt = hor_cnts[n-1];
            for (int i = n-2; i >= 0; i--) {
                hor_temp[i] = hor_temp[i+1] + cnt;
                cnt += hor_cnts[i];
            }
            // pick up the optimal col
            int min_h_val = INT_MAX;
            for (int i = 0; i < n; i++) {
                hor[i] += hor_temp[i];
                if (hor[i] < min_h_val) {
                    min_h_val = hor[i];
                }
            }
            
            // get the cost to each ver potition
            // ver: the cost of moving vertically to each row
            int ver[m];
            fill_n(ver, m, 0);
            
            // forward
            int ver_temp[m];
            ver_temp[0] = 0;
            cnt = ver_cnts[0];
            for (c = 1; c < m; c++) {
                ver_temp[c] = ver_temp[c-1] + cnt;
                cnt += ver_cnts[c];
            }
            for (c = 0; c < m; c++) {
                ver[c] += ver_temp[c];
            }
    
            //backward
            ver_temp[m-1]= 0;
            cnt = ver_cnts[m-1];
            for (c = m-2; c >= 0; c--) {
                ver_temp[c] = ver_temp[c+1] + cnt;
                cnt += ver_cnts[c];
            }
            // pick up the optimal row
            int min_v_val = INT_MAX;
            for (c = 0; c < m; c++) {
                ver[c] += ver_temp[c];
                if (ver[c] < min_v_val) {
                    min_v_val = ver[c];
                }
            }
    
            return min_h_val + min_v_val;
        }
    };

Log in to reply
 

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