algoadvance

Leetcode 63. Unique Paths II

Problem Statement

A robot is located at the top-left corner of an 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

Clarifying Questions

1. Constraints on the size of the grid?
   • The grid dimensions are m x n where m and n are at most 100.
2. What should be returned if the start or end point is an obstacle?
   • If the start or end point of the grid is an obstacle, the number of unique paths should be 0.
3. Nature of the grid?
   • The grid will always be filled with either 0 (free space) or 1 (obstacle).

Strategy

• Dynamic Programming Approach:
  • We can use dynamic programming to keep track of the number of ways to reach each cell.
  • If the cell has an obstacle, the number of ways to reach that cell is 0.
  • Otherwise, the number of ways to reach the cell (i, j) is the sum of the number of ways to reach the cell directly above it (i-1, j) and the number of ways to reach the cell directly to its left (i, j-1).
  • Initialize the starting cell dp[0][0] as 1 if it is not an obstacle. If it is an obstacle, return 0 immediately since no paths are possible.
  • The result will be the value in the bottom-right cell of the grid.

Time Complexity

• The time complexity of this approach is O(m * n) because we iterate through each cell of the grid exactly once.
• The space complexity is also O(m * n) due to the dp table.

Code

#include <vector>

class Solution {
public:
    int uniquePathsWithObstacles(std::vector<std::vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        
        // If the starting point is an obstacle, return 0
        if (obstacleGrid[0][0] == 1) return 0;
        
        // Initialize the dp grid with zeros
        std::vector<std::vector<long long>> dp(m, std::vector<long long>(n, 0));
        
        // Initialize the start position
        dp[0][0] = 1;
        
        // Fill the dp grid considering obstacles
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;  // If there's an obstacle, no paths go through here
                } else {
                    if (i > 0) dp[i][j] += dp[i-1][j];  // Paths from the top
                    if (j > 0) dp[i][j] += dp[i][j-1];  // Paths from the left
                }
            }
        }
        
        return dp[m-1][n-1];
    }
};

This solution initializes a DP table dp to store the number of unique paths to each cell and updates it iteratively based on the cells above and to the left, adjusting for obstacles. The final answer resides in dp[m-1][n-1].

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?