Easy to understand C++ O(n^2) solution with explanation why find median


  • 3

    Initially, I thought meeting point must be at a 0, which seems I was wrong, and I was overthinking. Later on, when I realized that people can meet at somebody's home 1, then it's much easier. To start with the most simple scenario, if now we only have two 1 on a straight line, then we know that meet at any point in between is the best. How about 3 1? We can meet at the middle 1. How about n 1 on a straight line? The best solution is to pair 1 by picking the leftmost and rightmost and go on, until we find the last pair or the middle one can't be paired, then it should give us the best answer here. How to prove that?

    1  0  0  0  1  0  0  1  1  0  0  1
    p1          p2       m  p2 m'    p1
    

    The best answer is actually the distance between all pairs of 1. In the example above, m is the best meeting point. So purpose we have another candidate m', since m' is in between pair p1, so p1 is not impacted. But m' is now outside of pair p2, ans we know that between two points, straight line is the shortest, so for m' which is beyond the two points, it's no longer making the shortest distance. That's why I was trying to pair 1 in the first place by using instincts. Yes, eventually, it converted to find the median index horizontally and vertically of 1.

    Let's look at another example, in the following example, there are two best meeting points

    1  0  0  0  1  0  0  1  1  0  0  1  1
    p1          p2       m  m        p2 p1
    

    Code

    class Solution {
    public:
        int minTotalDistance(vector<vector<int>>& grid) {
            if(!grid.size() || !grid[0].size()) return 0;
            int m = grid.size(), n = grid[0].size(), ans = 0;
            vector<int> hori, vert;
            
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++)
                    if(grid[i][j] == 1){ 
                        hori.push_back(i);
                        vert.push_back(j);
                    }
            }
            
            sort(hori.begin(), hori.end());
            sort(vert.begin(), vert.end());
            int imed = hori[hori.size() / 2];
            int jmed = vert[vert.size() / 2];
            
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++)
                    if(grid[i][j] == 1){
                        ans += abs(i - imed);
                        ans += abs(j - jmed);
                    } 
            }
            
            return ans;
        }
    };

Log in to reply
 

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