8ms C++ DP solution with O(mn) time & O(m + n) space


  • 0
    G

    My solution to the 1-D version of this problem is to calculate the distance sum to Position 0 first, then move the Position from 0 to 1, update the distance sum, and repeat to find the minimum distance sum.

    Moving Position from i to i + 1, the distance sum will be incremented by the number of the people in [0, i] and also decremented by the number of the people in [i + 1, n - 1].

    Thus, the DP transition equation is dist[i] = dist[i - 1] + #[0, i] - #[i + 1, n - 1], where dist[i] denotes the sum of the distances between each person's position and Position i, and #[i, j] denotes the number of people within position window [i, j].

    It is obvious that we can stop moving once the number of people in [0, i] is no less than the number in [i + 1, n - 1], i.e., #[0, i] - #[i + 1, n - 1] >= 0, which means we have reached the median.

    In order to count the number of people within a position range, we can use range sum (https://leetcode.com/problems/range-sum-query-immutable/) to deal with it.

    To solve the 2-D version of the problem, we can use a similar way.

    We first find the accumulated sums of the numbers of people y_count & x_count vertically and horizontally, respectively, and the distance sums y_dist & x_dist which represent the sum of the distance between each person's position to Row 0 and Column 0, respectively.

    Similarly, we find the minimum distance sum horizontally and vertically, and the answer will be the sum of both minimum distance.

    For example, the grid is

    1 0 0 0 1
    0 0 0 0 0
    0 0 1 0 0
    

    So the x_count will be [1, 1, 2, 2, 3], y_count will be [2, 2, 3], and the initial x_dist will be 0 + 4 + 2 = 6, the initial y_dist will be 0 + 0 + 2 = 2. Thus, the distance sums of each position will be

                  median
    median 6+2 5+2 4+2 | 5+2 6+2
        --------------------------
           6+3 5+3 4+3   5+3 6+3
           6+4 5+4 4+4   5+4 6+4
    

    Actually, what we do is to find the minimum separately:
    horizontally: 6, 6+1-(3-1)=5, 5+1-(3-1)=4 4+2-(3-2)=5, 5+2-(3-2)=6
    vertically: 2 2+2-(3-2) = 3, 3+2-(3-2)=4

    Therefore, the result is 4+2=6.

    class Solution {
    public:
        int minTotalDistance(vector<vector<int>>& grid) {
            int m = (int)grid.size(), n = m == 0 ? 0 : (int)grid[0].size();
            if (n == 0) return 0;
            int y_count[m] = {0}, x_count[n] = {0};
            int y_dist = 0, x_dist = 0;
            for (int i = 0; i != m; ++i) {
                y_count[i] = i == 0 ? 0 : y_count[i - 1];
                for (int j = 0; j != n; ++j) {
                    y_count[i] += grid[i][j];
                    x_count[j] += y_count[i] - (i == 0 ? 0 : y_count[i - 1]);
                    x_dist += grid[i][j] * j;
                    y_dist += grid[i][j] * i;
                }
            }
            int reduced = 0;
            for (int i = 0; i != m - 1 && (reduced = y_count[i] - (y_count[m - 1] - y_count[i])) < 0; ++i)
                y_dist += reduced;
                
            for (int j = 0; j != n - 1 && (reduced = x_count[j] - (x_count[n - 1] - x_count[j])) < 0; ++j)
                x_dist += reduced;
                
            return x_dist + y_dist;
        }
    };
    

Log in to reply
 

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