Java 5-liner O(|nuts|) Time O(1) Space

• Proof: Let the minimum distance from each nut to the tree be `a_1, ..., a_n` and let the minimum distance from each nut to the initial squirrel position be `b_1, ..., b_n`. Note that the minimum distance between two positions in the matrix is determined by their Manhattan distance.

Then, if the squirrel were to start at the tree, then the minimum total distance required to collect all the nuts is `2a_1 + ... + 2a_n`. However, since the squirrel starts elsewhere, we just need to substitute one of the `2a_i` terms with `a_i + b_i`. Or equivalently, we replace one of the `a_i` terms in the sum with `b_i`. To minimize the total sum value at the end, we choose `i` that maximizes `a_i - b_i`.

``````public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
int sum = 0, maxDiff = Integer.MIN_VALUE;
for (int[] nut : nuts) {
int dist = Math.abs(tree[0] - nut[0]) + Math.abs(tree[1] - nut[1]);
sum += 2*dist;
maxDiff = Math.max(maxDiff, dist - Math.abs(squirrel[0] - nut[0]) - Math.abs(squirrel[1] - nut[1]));
}
return sum - maxDiff;
}
``````

• Nice! Idk what the heck I was doing with this problem!

• maxDiff = Math.max(maxDiff, dist - Math.abs(squirrel[0] - nut[0]) - Math.abs(squirrel[1] - nut[1]));

Very smart. it is to find mosted saved distance, not the closest distance to squerral! I come up similar first step, but wrong algorithm second step.

• Rewritten in C++,

``````int minDistance(int height, int width, vector<int>& tree, vector<int>& squirrel, vector<vector<int>>& nuts) {
auto manDist = [](const vector<int>& v1, const vector<int>& v2) {return abs(v1[0]-v2[0]) + abs(v1[1]-v2[1]);};
const auto N = nuts.size();
auto sum = 0;
auto maxDiff = std::numeric_limits<int>::min();

for (auto i = 0; i < N; i++) {
auto tmp = manDist(nuts[i], tree);
sum += 2 * tmp;
maxDiff = max(maxDiff, tmp - manDist(squirrel, nuts[i]));
}

return sum - maxDiff;
}``````

• Thank you bro!

• Sharing my solution here with explanation:

``````public class Solution {
public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
int[] dist2tree = new int[nuts.length], dist2squir = new int[nuts.length];
int maxDiff = Integer.MIN_VALUE, sum2tree = 0;
for (int i = 0; i < nuts.length; i++) {
dist2tree[i] = Math.abs(tree[0] - nuts[i][0]) + Math.abs(tree[1] - nuts[i][1]);
sum2tree += dist2tree[i];
dist2squir[i] = Math.abs(squirrel[0] - nuts[i][0]) + Math.abs(squirrel[1] - nuts[i][1]);
int diff = dist2tree[i] - dist2squir[i];
if (diff > maxDiff)
maxDiff = diff;
}
return sum2tree * 2 - maxDiff;
}
}
``````

For `n` nuts, only `n-1` of them would contribute `2 * distance_of_nut[i]_to_tree` to the total distance. The other one, which is the first one picked up would contribute `distance_of_nut[i]_to_tree + distance_of_nut[i]_to_squirrel` to the total distance. To minimize the total distance, pick, as the first nut to pick up, the nut with the maximum `2 * distance_of_nut[i]_to_tree - (distance_of_nut[i]_to_tree + distance_of_nut[i]_to_squirrel)`.

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