3 ms java solution


  • 0
    F
    public int minPathSum(int[][] grid) {
            int rows=grid.length;
            int cols=grid[0].length;
            int[][] result=grid;
            //fill up first row. Each cell is just sum of itself and the previous cell
            for(int i=1;i<cols;i++){
                result[0][i]+=result[0][i-1];
            }
          //fill up the first column. Each cell is a sum of the cell above it
            for(int j=1;j<rows;j++){
                result[j][0]+=result[j-1][0];
            }
            //fill up rest of the cells. cell = cell + min (cell_above , cell_left)
            for(int i=1;i<rows;i++){
                for(int j=1;j<cols;j++){
                    result[i][j]+=Math.min(result[i-1][j],result[i][j-1]);
                }
            }
            return result[rows-1][cols-1];
        }
    

Log in to reply
 

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