Easy to understand concise O(n) solution with explanation


  • 0
    I

    Since squirel needs to travel to the tree every time after picking a nut, it needs to travel to the first nut, get it to the tree and then visit other nuts one by one. So total distance would be
    dist(squirrel,first_nut) + dist(fist_nut, tree) + 2 * sum(dist(nut,tree)) - 2 * dist(fist_nut, tree) = dist(squirrel,first_nut) - dist(fist_nut, tree) + 2 * sum(dist(nut,tree))
    Since sum(dist(nut,tree)) is constant, so we just need to minimize dist(squirrel,first_nut) - dist(fist_nut, tree) to select the first nut.

    int dist(int x1, int y1, int x2, int y2) {return abs(x1-x2) + abs(y1-y2);}
    int minDistance(int height, int width, vector<int>& tree, vector<int>& squirrel, vector<vector<int>>& nuts){
       int d2 = 0;
       int mn = INT_MAX;
       for(int i = 0; i < nuts.size(); ++i) {
          d2 += dist(nuts[i][0],nuts[i][1],tree[0],tree[1])*2;
          mn = min(mn,dist(squirrel[0],squirrel[1],nuts[i][0],nuts[i][1]) - dist(tree[0],tree[1],nuts[i][0],nuts[i][1]));
       }
       return mn + d2;
    }
    

Log in to reply
 

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