algoadvance

Leetcode 63. Unique Paths II

Problem Statement

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space are marked as 1 and 0 respectively in the grid.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

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

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[0].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

Clarifying Questions

1. Can the robot start or end on an obstacle?
   • No. If the start or end position contains an obstacle, there are zero unique paths.
2. Is the grid always rectangular?
   • Yes, it is specified by its dimensions m x n.
3. Will there always be at least one cell in the grid?
   • Yes, the constraints guarantee 1 <= m, n.

Strategy

We will use a dynamic programming approach to solve this problem. Here is the step-by-step strategy:

1. Initialize DP Table: We will create a 2D DP array dp of the same dimensions as obstacleGrid.
2. Base Case:
   • If the start cell (top-left corner) has an obstacle, return 0.
   • Otherwise, set dp[0][0] to 1.
3. Fill the DP Table:
   • For each cell in the grid:
     • if it has an obstacle, set dp[i][j] to 0.
     • Otherwise, set dp[i][j] to the sum of the values from the cell directly above (dp[i-1][j]) and the cell directly to the left (dp[i][j-1]), handling boundary conditions where i or j is 0.
4. The value in the bottom-right corner of the DP table will give the total number of unique paths.

Code

public class UniquePathsII {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        // If the start or end cell has an obstacle, return 0.
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }

        int[][] dp = new int[m][n];

        // Initial position without an obstacle
        dp[0][0] = 1;

        // Fill the first column
        for (int i = 1; i < m; i++) {
            dp[i][0] = (obstacleGrid[i][0] == 1) ? 0 : dp[i-1][0];
        }

        // Fill the first row
        for (int j = 1; j < n; j++) {
            dp[0][j] = (obstacleGrid[0][j] == 1) ? 0 : dp[0][j-1];
        }

        // Fill the rest of the dp array
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }

        return dp[m-1][n-1];
    }
}

Time Complexity

• Time Complexity: O(m * n) because we have to iterate through each cell in the grid once.
• Space Complexity: O(m * n) for the DP table. However, space usage can be optimized to O(n) if we store only the current and previous row.

By following this strategy and code, we will be able to find the number of unique paths in a grid considering obstacles efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?