O(n) Time,O(n) Space, inspired by 238.Product of Array Except Self, no Math


  • 1
    public class Solution {
        public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
            int[] dp=new int[nuts.length];
            int pre=0;
            int min=Integer.MAX_VALUE;
            
            for(int i=0;i<nuts.length;i++){
                dp[i]+=dist(nuts[i],squirrel)+pre;
                pre+=dist(nuts[i],tree);
            }
            
            pre=0;
            for(int i=nuts.length-1;i>=0;i--){
                dp[i]+=pre;
                pre+=dist(nuts[i],tree);
                min=Math.min(min,dp[i]);
            }
            
            return min+pre;
        }
        
        public int dist(int[] n1,int[] n2){
            return Math.abs(n1[0]-n2[0])+Math.abs(n1[1]-n2[1]);
        }
    }

  • 0
    M
    This post is deleted!

Log in to reply
 

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