SimuVedaAlgorithms Lab Open in the lab

Dynamic programming / Intermediate

Unique Paths with Obstacles Visualizer

You can only enter a cell from above or from the left, so paths(r, c) = paths(r − 1, c) + paths(r, c − 1). An obstacle has 0 paths through it.

Start the Unique Paths with Obstacles simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(R·C)
Average timeO(R·C)
Worst timeO(R·C)
Extra spaceO(R·C)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Count the right/down paths from the top-left to the bottom-right. █ is an obstacle.
  2. The start has exactly 1 path: stand still.
  3. (0, 1) = from above 0 + from the left 1 = 1.
  4. (0, 2) = from above 0 + from the left 1 = 1.
  5. (0, 3) = from above 0 + from the left 1 = 1.
  6. (1, 0) = from above 1 + from the left 0 = 1.
  7. (1, 1) is an obstacle: 0 paths go through it.
  8. (1, 2) = from above 1 + from the left 0 = 1.
  9. (1, 3) = from above 1 + from the left 1 = 2.
  10. (2, 0) = from above 1 + from the left 0 = 1.
  11. (2, 1) = from above 0 + from the left 1 = 1.
  12. (2, 2) = from above 1 + from the left 1 = 2.
  13. (2, 3) = from above 2 + from the left 2 = 4.
  14. (3, 0) = from above 1 + from the left 0 = 1.
  15. (3, 1) = from above 1 + from the left 1 = 2.
  16. (3, 2) is an obstacle: 0 paths go through it.
  17. (3, 3) = from above 4 + from the left 0 = 4.
  18. There are 4 paths to the bottom-right corner.

Try it with your own input →

2D DP: unique paths with obstacles in Java, Python, C++, C and JavaScript

int uniquePaths(int[][] g) {
  int R = g.length, C = g[0].length;
  int[][] dp = new int[R][C];
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++) {
      if (g[r][c] == 1) dp[r][c] = 0;
      else if (r == 0 && c == 0) dp[r][c] = 1;
      else dp[r][c] = (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
    }
  return dp[R - 1][C - 1];
}
def unique_paths(g):
    R, C = len(g), len(g[0])
    dp = [[0] * C for _ in range(R)]
    for r in range(R):
        for c in range(C):
            if g[r][c] == 1:
                dp[r][c] = 0
            elif r == 0 and c == 0:
                dp[r][c] = 1
            else:
                dp[r][c] = (dp[r - 1][c] if r > 0 else 0) + (dp[r][c - 1] if c > 0 else 0)
    return dp[R - 1][C - 1]
int uniquePaths(const vector<vector<int>>& g) {
  int R = g.size(), C = g[0].size();
  vector<vector<int>> dp(R, vector<int>(C, 0));
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++) {
      if (g[r][c] == 1) dp[r][c] = 0;
      else if (r == 0 && c == 0) dp[r][c] = 1;
      else dp[r][c] = (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
    }
  return dp[R - 1][C - 1];
}
int uniquePaths(int R, int C, int g[R][C]) {
  int dp[R][C];
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++) {
      if (g[r][c] == 1) dp[r][c] = 0;
      else if (r == 0 && c == 0) dp[r][c] = 1;
      else dp[r][c] = (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
    }
  return dp[R - 1][C - 1];
}
function uniquePaths(g) {
  const R = g.length, C = g[0].length;
  const dp = Array.from({ length: R }, () => new Array(C).fill(0));
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++) {
      if (g[r][c] === 1) dp[r][c] = 0;
      else if (r === 0 && c === 0) dp[r][c] = 1;
      else dp[r][c] = (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
    }
  return dp[R - 1][C - 1];
}

In an interview

LeetCode 63, Unique Paths II. Without obstacles it is 62 Unique Paths; with costs it becomes 64 Minimum Path Sum.

Fill row by row and you only ever need the previous row, so one 1D array of size C is enough.

More dynamic programming