Simple Java DP solution - O(mn) time complexity, Constant space complexity


  • 1
    S

    Java solution modifying the "grid" in place to avoid any extra storage.
    The main recurrence of the DP is in the third loop and pretty easy to understand.

    public class Solution {
        public int minPathSum(int[][] grid) {
            
            if(grid.length == 0){
                return 0;
            }
            
            int m=grid.length;
            int n=grid[0].length;
    
            //Sum across first column
            for(int i=1;i<m;i++){
                grid[i][0] += grid[i-1][0];
            }
            
            //Sum across first row
            for(int i=1;i<n;i++){
                grid[0][i] += grid[0][i-1];
            }
            
            //For every other element, add to it Min(cell above, cell to the left)
            for(int i=1;i<m;i++){
                for(int j=1;j<n;j++){
                    grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
                }
            }
            
            return grid[m-1][n-1];
        }
    }

Log in to reply
 

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