C++ O(n) solution with detailed explanation


  • 0
    D

    This a pure math problem, the only difference is which nut as the first target for the squirrel to pick.
    Frist, we calculate the distance from squirrel and trees to all nuts and store them in two different arrays.
    Second, we calculate the total distance from tree to nuts.
    Third, final step to find the solution.
    We loop to pick each nut as the first target. What we should do is to subtract the distance from tree to this nuts and plus the distance from this nut to the squirrel.

    class Solution {
    public:
        int minDistance(int height, int width, vector<int>& tree, vector<int>& squirrel, vector<vector<int>>& nuts) {
            vector<int> squi2nuts;
            vector<int> tree2nuts;
            int total_dis = 0;
            for(int i = 0; i < nuts.size(); i++){
                // calculate the distrance from squirrel to nuts
                squi2nuts.push_back(abs(nuts[i][0] - squirrel[0]) + abs(nuts[i][1] - squirrel[1]));
                // calculate total distance, double the distance from tree to all nuts
                total_dis += (abs(nuts[i][0] - tree[0]) + abs(nuts[i][1] - tree[1])) * 2;
                // calculate the distrance from tree to nuts
                tree2nuts.push_back(abs(nuts[i][0] - tree[0]) + abs(nuts[i][1] - tree[1]));
            }
            int min_dis = INT_MAX;
            for(int i = 0; i < tree2nuts.size(); i++){
                min_dis = min(min_dis, total_dis - tree2nuts[i] + squi2nuts[i]);
            }
            return min_dis;
        }
    };
    

Log in to reply
 

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