C++ 6ms DP, O(mn) time, O(m+n) space with explanations


  • 0
    H

    If the meet distance at point (i, j) is X, people from col[0] to col[j] is a, people from col[j+1] to col[n-1] is b, the meet distance at point (i, j+1) is X + a - b. Because b = total - a, X + a - b => X + 2a - total

    Same rule applied to rows.

    So, use two vectors vector<int> row and vector<int> col . row[i] and col[j] store the accumulative number of people to row i and column j respectively.

    In the meantime of calculating the accumulative values, get the meet distance base at point (0, 0) and total people

    Finally, traverse all points and calculate the meet distance at each point and find the minimum distance.

        int minTotalDistance(vector<vector<int>>& grid) {
            int m = grid.size();
            if (m == 0) return 0;
            int n = grid[0].size();
            vector<int> row(m, 0);
            vector<int> col(n, 0);
            int base = 0;
            int total = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    row[i] += grid[i][j];
                    col[j] += grid[i][j];
                    if (grid[i][j]) base += i + j;
                    total += grid[i][j];
                }
            }
            for (int i = 1; i < m; i++) row[i] += row[i-1];
            for (int i = 1; i < n; i++) col[i] += col[i-1];
            
            int res = base;
            for (int i = 0; i < m; i++) {
                base += i > 0 ? 2 * row[i-1] - total : 0;
                int cur = base;
                for (int j = 0; j < n; j++) {
                    cur += j > 0 ? 2 * col[j-1] - total : 0;
                    res = min(res, cur);
                }
            }
            return res;
        }
    

Log in to reply
 

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