63. Unique Paths II

Time: O(m x n)

Space: O(m x n)

Intuition

Same DP as Unique Paths I, but cells with obstacles are set to 0 (no paths through them). The recurrence is: dp[i][j] = (obstacleGrid[i][j]==1) ? 0 : dp[i-1][j] + dp[i][j-1].

Algorithm

1If start or end has an obstacle, return 0.
2Fill dp[0][j]=1 for all j until an obstacle is hit (all 0 after the obstacle).
3Fill dp[i][0]=1 for all i until an obstacle is hit.
4For each interior cell: dp[i][j] = (obstacle) ? 0 : dp[i-1][j] + dp[i][j-1].
5Return dp[m-1][n-1].

Example Walkthrough

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

1.First row: dp=[1,1,1]. First col: dp[1][0]=1, dp[2][0]=1.
2.dp[1][1]=0 (obstacle). dp[1][2]=dp[0][2]+0=1.
3.dp[2][1]=dp[1][1]+dp[2][0]=0+1=1. dp[2][2]=dp[1][2]+dp[2][1]=1+1=2.

Output: 2

Common Pitfalls

•Stop filling the first row/column once an obstacle is encountered - all cells beyond it are unreachable.

63.cs

// Approach: 2D DP extending the standard Unique Paths solution to handle obstacles.
// dp[i][j] = number of distinct paths to reach cell (i,j) from (0,0).
// If obstacleGrid[i][j] == 1, set dp[i][j] = 0 (no paths through an obstacle).
// Otherwise dp[i][j] = dp[i-1][j] + dp[i][j-1] (paths from above + paths from left).
// Initialise the first row and column carefully — any obstacle blocks all cells beyond it.
// Time: O(m x n) Space: O(m x n); reducible to O(n) with a rolling row.

public class Solution
{
    public int UniquePathsWithObstacles(int[][] obstacleGrid)
    {
        int m = obstacleGrid.Length;
        int n = obstacleGrid[0].Length;
        // int[][] dp = new int[m][];
        // for(int i = 0; i < m; i++)
        // {
        //     int[] arr = new int[n];
        //     Array.Fill(arr, -1);
        //     dp[i] = arr;
        // }
        //return topdown(m - 1, n - 1, obstacleGrid, dp);
        return tabulation(m - 1, n - 1, obstacleGrid);
    }

    private int topdown(int row, int col, int[][] grid, int[][] dp)
    {
        if (row >= 0 && col >= 0 && grid[row][col] == 1)
            return 0;

        if (row == 0 && col == 0)
            return 1;

        if (row < 0 || col < 0)
            return 0;

        if (dp[row][col] != -1)
            return dp[row][col];

        int cnt = 0;
        cnt += topdown(row - 1, col, grid, dp);
        cnt += topdown(row, col - 1, grid, dp);
        dp[row][col] = cnt;

        return cnt;
    }

    private static int tabulation(int row, int col, int[][] grid)
    {
        int[] prev = new int[col + 1];

        for (int i = 0; i <= row; i++)
        {
            int[] curr = new int[col + 1];
            for (int j = 0; j <= col; j++)
            {
                if (grid[i][j] == 1)
                    curr[j] = 0;
                else if (i == 0 && j == 0)
                    curr[j] = 1;
                else
                {
                    int up = 0, left = 0;
                    if (i > 0)
                        up = prev[j];
                    if (j > 0)
                        left = curr[j - 1];

                    curr[j] = up + left;
                }
            }
            prev = curr;
        }

        return prev[col];
    }
}

Was this solution helpful?