in-situ solution using array grid itself


  • 0
    M

    Many solutions have not realized that we do not need another m*n array space to remember the minimum path to a certain grid point, the path value itself can be stored to the grid because we search the grid from left to right and up to down.
    Here is my solution

    int minPathSum(int** grid, int gridRowSize, int gridColSize) {
        int i, j;
        for (i = 0; i < gridRowSize; i++){
        	for (j = 0; j < gridColSize; j++){
        		if (i == 0 && j == 0)
        			continue;
        		if (i == 0)
        			grid[i][j] += grid[i][j-1];
        		else if (j == 0)
        			grid[i][j] += grid[i-1][j];
        		else
        			grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
        	}
        }
        return grid[i-1][j-1];
    }
    
    int min(int a, int b){
    	return (a<b)? a:b;
    }
    

Log in to reply
 

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