# Easy to understand concise O(n) solution with explanation

• 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;
}
``````

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