Unique Paths II

Same question just with Obstacles in the grid. Refer: Space optimization

1. Recursive Solution

TC: O(2^(m + n)) — This is because each recursive call has two choices, leading to an exponential time complexity. SC: O(m + n) for the recursion stack.

public class UniquePathsII {
 
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // If the starting point or ending point has an obstacle, no path is possible.
        if (obstacleGrid[0][0] == 1 || obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) {
            return 0;
        }
        return findPaths(obstacleGrid, 0, 0);
    }
 
    // Recursive function to find paths.
    private int findPaths(int[][] grid, int row, int col) {
        // If we are out of bounds or hit an obstacle, return 0 (no path).
        if (row >= grid.length || col >= grid[0].length || grid[row][col] == 1) {
            return 0;
        }
 
        // If we reach the bottom-right corner, there's one valid path.
        if (row == grid.length - 1 && col == grid[0].length - 1) {
            return 1;
        }
 
        // Explore the path by moving down and right.
        int downPaths = findPaths(grid, row + 1, col);
        int rightPaths = findPaths(grid, row, col + 1);
 
        // Total paths are the sum of the paths from down and right directions.
        return downPaths + rightPaths;
    }
 
    public static void main(String[] args) {
        UniquePathsII solution = new UniquePathsII();
        int[][] obstacleGrid = {
            {0, 0, 0},
            {0, 1, 0},
            {0, 0, 0}
        };
        System.out.println(solution.uniquePathsWithObstacles(obstacleGrid));  // Output: 2
    }
}

2. Dp Solution

TC: O(m x n) — Each cell is computed once, making it much more efficient. SC: O(m x n) for the dp array

public class UniquePathsIIDP {
 
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
 
        // If the starting or ending cell has an obstacle, return 0.
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }
 
        // DP array to store the number of ways to reach each cell.
        int[][] dp = new int[m][n];
 
        // Initialize the starting point.
        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 table.
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;  // If there's an obstacle, no paths to this cell.
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  // Sum of paths from top and left.
                }
            }
        }
 
        // The bottom-right corner will contain the number of unique paths.
        return dp[m - 1][n - 1];
    }
 
    public static void main(String[] args) {
        UniquePathsIIDP solution = new UniquePathsIIDP();
        int[][] obstacleGrid = {
            {0, 0, 0},
            {0, 1, 0},
            {0, 0, 0}
        };
        System.out.println(solution.uniquePathsWithObstacles(obstacleGrid));  // Output: 2
    }
}

3. Space optimized

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
 
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int[] prev = new int[n];
 
        for (int j = n - 1; j >= 0; j--) {
            if(obstacleGrid[m - 1][j] == 1){
                prev[j] = 0;
            } else{
                prev[j] = (j == n - 1) ? 1 : prev[j + 1];
            }
        }
		
		// Fill the grid from bottom to top
		for(int i = m - 2; i >= 0; i--){
			
			int[] curr = new int[n];
            // Initialize the last column for the current row (only one way to reach the destination by moving down)
            if(obstacleGrid[i][n - 1] != 1){
                curr[n - 1] = prev[n - 1];
            } else{
                curr[n - 1] = 0;
            }
			 
			// Update the current row based on the values from the previous row
			for(int j = n - 2; j >= 0; j--){
                if(obstacleGrid[i][j] != 1){
                    curr[j] = curr[j + 1] + prev[j]; // Sum of ways from the cell to the right and the cell directly below
                } else{
                    curr[j] = 0;
                }
				
			}
			
			prev = curr;
		}
		return prev[0];        
    }
}