Lintcode 912: Best Meeting Point

https://www.lintcode.com/problem/best-meeting-point/description

Notes

This question can be viewed as a follow up of this question Leetcode 462. Minimum Moves to Equal Array Elements II.

The only difference is that the current question is a 2D case, instead of 1D.

So we just can separate it into two 1Ds. Why can we do this?

Because we need to calculate the Manhattan distance, which is the linear sum of 2 directions.

Once we record the x and y coordinates separately, we can treat it as Leetcode 462.

Leetcode 462 can be solved by binary search for a "u" shape sorted list.

The argument is listed below:

Let say the answer is in the range of [left, right].

Define mid = left + (right - left) / 2;

If dis(mid) < dis(mid-1), then the answer should be in [mid, right];
else, it should be in [left, mid-1].

See the code below:

class Solution {
public:
    int minTotalDistance(vector<vector<int>> &grid) {
        int res = 0;
        if(!grid.size() || !grid.front().size()) return res;
        int m = grid.size(), n = grid.front().size();
        vector<int> xs, ys;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 1) {
                    xs.push_back(i);
                    ys.push_back(j);
                }
            }
        }
        int x = f1(xs, 0, m-1), y = f1(ys, 0, n-1);
        return cal(xs, x) + cal(ys, y);
    }

private:
    int f1(vector<int>& vs, int x, int y) {
        if(x==y) return x;
        if(x+1 == y) {
            return cal(vs, x) < cal(vs, y) ? x : y;
        }
        int mid = x + (y - x) / 2;
        if(cal(vs, mid) < cal(vs, mid-1)) return f1(vs, mid, y);
        return f1(vs, x, mid-1);
    }
    int cal(vector<int>& vs, int v) {
        int res = 0;
        for(auto &a : vs) res += abs(a - v);
        return res;
    }
};