2ms Java DP solution, O(m*n) time, O(1) space; beats 98%


  • 0
    S
    public class Solution {
        public int[][] helper(int[][] grid, int m, int n){
            while(n > 0){
                if(m == grid.length-1)
                    grid[m][n-1] = grid[m][n-1]+grid[m][n];
                else grid[m][n-1] = grid[m][n-1] + Math.min(grid[m][n], grid[m+1][n-1]);
                n--;
            }
            return grid;
        }
        public int minPathSum(int[][] grid) {
            if(grid.length == 0) return 0;
            int m = grid.length-1, n = grid[0].length-1;
            while(m >= 0){
                grid = helper(grid, m, n);
                m--;
                if(m >= 0)
                    grid[m][n] = grid[m+1][n] + grid[m][n];
            }
            return grid[0][0];
        }
    }
    

Log in to reply
 

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