Share my Java solution: O(m*n) time complexity, no extra space.


  • 5
    L

    Obviously, this is a DP problem.

    Let F(i,j) denotes the paths from top left to cell (i,j).

    If cell (i,j) has an obstacle, then F(i,j) = 0.
    else

    for j>0, F(0,j) = F(0,j-1)

    for i>0, F(i,0) = F(i-1,0)

    for i>0&&j>0, F(i,j) = F(i-1,j)+F(i,j-1)

    We can take advantage of the obstacle array without using extra space.

        if(obstacleGrid==null||obstacleGrid.length==0)
        	return 0;
    
        for(int i=0;i<obstacleGrid.length;i++)
        	for(int j=0;j<obstacleGrid[0].length;j++)
        	{
        		if(i==0)
        		{
        			if(j==0)
        				obstacleGrid[0][0] = 1 - obstacleGrid[0][0];
        			else
        				obstacleGrid[0][j] = obstacleGrid[0][j]==1?0:obstacleGrid[0][j-1];
        		}
        		else 
        		{
        			if(j==0)
        				obstacleGrid[i][0] = obstacleGrid[i][0]==1?0:obstacleGrid[i-1][0];
        			else 
        				obstacleGrid[i][j] = obstacleGrid[i][j]==1?0:(obstacleGrid[i-1][j]+obstacleGrid[i][j-1]);
    			}
        	}
        return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];

Log in to reply
 

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