Java O(n) Space


  • 0
    H
    public class Solution {
        public int minPathSum(int[][] grid) {
            int m = grid.length;
            if( m == 0) return 0;
            int n = grid[0].length;
            int[] arr = new int[n + 1];
            
            for(int i = 0; i < m ; i++)
            {
                for(int j = 0 ; j < n; j++)
                {
                    if(i == 0)
                        arr[j] = grid[0][j] + (j < 1 ? 0 : arr[j-1]);
                    else arr[j] = grid[i][j] + Math.min(j > 0 ? arr[j-1]: arr[j], arr[j]);
                }
            }
            
            return arr[n-1];
        }
    }
    

Log in to reply
 

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