Unique Paths II

NeetCode: Unique Paths II · LeetCode: 63. Unique Paths II · Difficulty: Medium

A robot starts at the top-left of an m x n grid and wants to reach the bottom-right, moving only right or down. Cells containing 1 are obstacles the robot cannot enter; cells containing 0 are free. Return the number of distinct paths.

Example

Text

Input:  grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]    Output: 2
Input:  grid = [[0, 1], [0, 0]]                     Output: 1
Input:  grid = [[1, 0]]                             Output: 0   (start blocked)

Brute force: plain recursion

The number of paths from (i, j) is the number of paths from the cell below plus the number from the cell to the right, and it is 0 if the cell is an obstacle or off the grid. Reaching the goal counts as one path. Each call branches in two, so the running time is exponential (O(2^(m+n))): the same cell is re-counted for every route that leads to it.

Java

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) return 0;
        return go(obstacleGrid, 0, 0);
    }

    private int go(int[][] g, int i, int j) {
        if (i >= g.length || j >= g[0].length || g[i][j] == 1) return 0;
        if (i == g.length - 1 && j == g[0].length - 1) return 1;
        return go(g, i + 1, j) + go(g, i, j + 1);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.uniquePathsWithObstacles(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}));
        System.out.println(s.uniquePathsWithObstacles(new int[][]{{0, 1}, {0, 0}}));
        System.out.println(s.uniquePathsWithObstacles(new int[][]{{1, 0}}));
    }
}

Output

2
1
0

Time: O(2^(m+n)). Space: O(m + n) recursion depth.

Better: memoization

Cache the count for each cell so it is computed only once. There are m * n cells, each combining two cached values. The cache is an int[][] filled with -1 for "not computed yet", because a real count is never negative.

Java

import java.util.Arrays;

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) return 0;
        int[][] memo = new int[obstacleGrid.length][obstacleGrid[0].length];
        for (int[] row : memo) Arrays.fill(row, -1);
        return go(obstacleGrid, 0, 0, memo);
    }

    private int go(int[][] g, int i, int j, int[][] memo) {
        if (i >= g.length || j >= g[0].length || g[i][j] == 1) return 0;
        if (i == g.length - 1 && j == g[0].length - 1) return 1;
        if (memo[i][j] != -1) return memo[i][j];
        int res = go(g, i + 1, j, memo) + go(g, i, j + 1, memo);
        memo[i][j] = res;
        return res;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.uniquePathsWithObstacles(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}));
        System.out.println(s.uniquePathsWithObstacles(new int[][]{{0, 1}, {0, 0}}));
        System.out.println(s.uniquePathsWithObstacles(new int[][]{{1, 0}}));
    }
}

Output

2
1
0

Time: O(m * n). Space: O(m * n).

Optimal: one-row DP

Let dp[j] be the number of paths reaching column j of the current row. A free cell is reached from above (dp[j], the old value) or from the left (dp[j-1], already updated); an obstacle cell has 0 paths. Seed the start with 1 (or 0 if it is an obstacle) and sweep row by row.

Java

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) return 0;
        int n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for (int[] row : obstacleGrid) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.uniquePathsWithObstacles(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}));
        System.out.println(s.uniquePathsWithObstacles(new int[][]{{0, 1}, {0, 0}}));
        System.out.println(s.uniquePathsWithObstacles(new int[][]{{1, 0}}));
    }
}

Output

2
1
0

Time: O(m * n). Space: O(n).

For the first row, dp[j] starts at 0 for j > 0, so it only becomes 1 by inheriting from the left, and an obstacle resets everything to its right to 0. That is exactly the "once blocked, the rest of the row is unreachable" behaviour. LeetCode guarantees the answer fits in a 32-bit int; int addition wraps silently on overflow, so a variant without that guarantee needs long.