4 ms Java solution with O(mn) time complexity and no space


  • 0
    public int minPathSum(int[][] a) {
            for(int i=1;i<a.length;i++){
                a[i][0] = a[i][0]+a[i-1][0];
            }
            for(int i=1;i<a[0].length;i++){
                a[0][i] = a[0][i]+a[0][i-1];
            }
            
            for(int i=1;i<a.length;i++){
                for(int j=1;j<a[0].length;j++){
                    a[i][j] = a[i][j] + Math.min(a[i-1][j], a[i][j-1]);
                }
            }
            return a[a.length-1][a[0].length-1];
        }```````

Log in to reply
 

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