Reference: Problem I & Problem II
Difficulty: Medium

My Post:

Problem

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).

How many possible unique paths are there?

Note: m and n will be at most 100.

Example: 

1
2
3
4
5
6
7
8
Input: m = 1, n = 1
Output: 1

Input: m = 3, n = 2
Output: 3

Input: m = 7, n = 3
Output: 28

Analysis

Recursion

Check out the comments.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Define: opt(i, j) the number of ways to the point (i, j)
// (0, 0) is the starting point, (m - 1, n - 1) is the finish point
// Recurrence: opt(i, j) = opt(i - 1, j) + opt(i, j - 1)
// Init: opt(0, 0) = 1, opt(0, j) = opt(i, 0) = 1
public int uniquePaths(int m, int n) {
  if (m == 0 || n == 0) {
    throw new IllegalArgumentException("m or n can't be 0");
  }
  return numPaths(m - 1, n - 1);
}

private int numPaths(int i, int j) {
  if (i == 0 || j == 0) { // includes the row 0 and col 0
    return 1;
  }
  return numPaths(i - 1, j) + numPaths(i, j - 1);
}

Time: $O(2^{M + N})$
Space: $O(M + N)$

Recurrence Tree for complexity analysis:

DP (Top-down with Memoization)

Use an 2D array mem to do memoization.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int uniquePaths(int m, int n) {
  if (m == 0 || n == 0) {
    throw new IllegalArgumentException("m or n can't be 0");
  }
  int[][] mem = new int[m][n];
  for (int i = 0; i < m; ++i) { // init
    for (int j = 0; j < n; ++j) {
      mem[i][j] = -1;
    }
  }
  return numPaths(m - 1, n - 1, mem);
}

private int numPaths(int i, int j, int[][] mem) {
  if (i == 0 || j == 0) {
    return 1;
  }
  if (mem[i - 1][j] == -1) mem[i - 1][j] = numPaths(i - 1, j, mem);
  if (mem[i][j - 1] == -1) mem[i][j - 1] = numPaths(i, j - 1, mem);
  return mem[i - 1][j] + mem[i][j - 1];
}

Time: $O(MN)$ where $MN$ is the number of subproblems.
Space: $O(MN)$

DP (Bottom-up)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int uniquePaths(int m, int n) {
  if (m == 0 || n == 0) {
    throw new IllegalArgumentException("m or n can't be 0");
  }
  int[][] dp = new int[m][n];
  // init
  for (int i = 0; i < m; ++i) dp[i][0] = 1;
  for (int i = 0; i < n; ++i) dp[0][i] = 1;
  // dp
  for (int i = 1; i < m; ++i) {
    for (int j = 1; j < n; ++j) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}

Time: $O(MN)$
Space: $O(MN)$

DP (Bottom-up, Linear Space)

Reduce the $O(MN)$ space complexity to $O(N)$ (a row) or $O(M)$ (a column). In terms of a row, we would update dp[j] by its old value plus dp[j - 1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int uniquePaths(int m, int n) {
  if (m == 0 || n == 0) {
    throw new IllegalArgumentException("m or n can't be 0");
  }
  int[] dp = new int[n]; // row
  // init
  for (int i = 0; i < n; ++i) dp[i] = 1;
  // dp
  for (int i = 1; i < m; ++i) {
    for (int j = 1; j < n; ++j) {
      dp[j] = dp[j] + dp[j - 1];
    }
  }
  return dp[n - 1];
}

Time: $O(MN)$
Space: $O(N)$ or $O(M)$

Unique Paths II (with Obstacles)

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

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

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input:
[
  [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

DP (Bottom-up)

The problem is very great. Check out the picture below. Here are some points to be considered carefully:

  • What two surrounding cells are affected if a cell is blocked?
    • Do we need to change the recurrence in the code?
    • No. If blocked, just setting dp[i][j] as $0$ is all we need.
  • What happens if the starting point or the finish point is blocked?
  • In the initial step, what happens to its following cells if a cell is blocked?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  // Assume m > 0 and n > 0
  int m = obstacleGrid.length, n = obstacleGrid[0].length;
  int[][] dp = new int[m][n];
  // init
  dp[0][0] = (obstacleGrid[0][0] == 1) ? 0 : 1; // check starting point; finish point will be considered.
  for (int i = 1; i < m; ++i) {
    if (obstacleGrid[i][0] == 1) dp[i][0] = 0;
    else dp[i][0] = dp[i - 1][0];  // if there is an obstacle, the following cell cannot be reached (= 0)
  }
  for (int i = 1; i < n; ++i) {
    if (obstacleGrid[0][i] == 1) dp[0][i] = 0;
    else dp[0][i] = dp[0][i - 1];
  }
  // dp
  for (int i = 1; i < m; ++i) {
    for (int j = 1; j < n; ++j) {
      if (obstacleGrid[i][j] == 1) dp[i][j] = 0; // blocked
      else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}

Time: $O(MN)$
Space: $O(MN)$

DP (Bottom-up, Linear Space)

We can reduce the space complexity too, but be careful when actually writing the code! In the row case, we need check if a cell at the first column is blocked in the dp step every time, which is usually forgotten.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  // Assume m > 0 and n > 0
  int m = obstacleGrid.length, n = obstacleGrid[0].length;
  int[] dp = new int[n]; // a row
  // init
  dp[0] = (obstacleGrid[0][0] == 1) ? 0 : 1; // check starting point; finish point is considered.
  for (int i = 1; i < n; ++i) {
    if (obstacleGrid[0][i] == 1) dp[i] = 0;
    else                         dp[i] = dp[i - 1];
  }
  // dp
  for (int i = 1; i < m; ++i) {
    if (obstacleGrid[i][0] == 1) dp[0] = 0; // should check the first cell each time
    for (int j = 1; j < n; ++j) {
      if (obstacleGrid[i][j] == 1) dp[j] = 0; // blocked
      else                         dp[j] = dp[j - 1] + dp[j];
    }
  }
  return dp[n - 1];
}

Time: $O(MN)$
Space: $O(N)$ or $O(M)$