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


  • 21

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

  • 0

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


  • 3
    A

    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.


  • 0
    G

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

  • 0
    F

    Thank you bro!


  • 0

    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).


Log in to reply
 

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