Where does my logic go wrong? [Time limit exceeded]


  • 0
    R
    public class Solution {
        public int minPathSum(int[][] grid) {
    		 if(grid == null || grid.length==0) return 0;
    	     return nextSum(0,0,grid);
    	 }
    	 
    	 public int nextSum(int row, int col,int[][] grid){
    		 int rows = grid.length;
    		 int cols = grid[0].length;
    		 int rowMove = Integer.MAX_VALUE, colMove = Integer.MAX_VALUE;
    		 if(row==rows-1 && col == cols-1) return grid[row][col];
    		if(row<rows-1){
    			 rowMove = grid[row][col] + nextSum(row+1,col,grid);
    		 }
    		 if(col<cols-1){
    			 colMove = grid[row][col] + nextSum(row, col+1, grid);
    		 }
    		 return Math.min(rowMove, colMove);
    	 }
    }

  • 0
    R

    Self resolved:

    I shouldn't have calculated from the last element, the min from the back may not necessarily the min in the front.

    Accepted version:

      public int minPathSum(int[][] grid) {
    
    	 if(grid == null || grid.length==0 ||grid[0].length==0) return 0;
    	 int rows = grid.length, cols = grid[0].length;
    	 int[] temp = new int[cols];
    	 
    	 for(int i=0;i<rows;i++){
    		 for(int j=0;j<cols;j++){
    			 if(i==0) { 
    				 temp[j] = (j==0) ? grid[0][0] : temp[j-1] + grid[i][j];
    			 }
    			 else if(j==0) temp[j] += grid[i][j]; 
    			 else temp[j] = Math.min(temp[j-1], temp[j]) + grid[i][j]; 
    		 
    	 }
    	 
    	 return temp[cols-1];
     }

Log in to reply
 

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