O(m*n) simple java solution


  • 0
    S
    public class Solution {
        public int minPathSum(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            
            for(int i=1; i<m; i++) {
                grid[i][0] += grid[i-1][0];
            }
            for(int i=1; i<n; i++) {
                grid[0][i] += grid[0][i-1];
            }
            
            int min = 0;
            for(int i=1; i<m; i++) {
                for(int j=1; j<n; j++) {
                    min = Math.min(grid[i][j-1], grid[i-1][j]);
                    grid[i][j] += min;
                }
            }
            
            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.