Unique Paths

​A robot is located at the top-left corner of a m x n grid (marked as ‘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 as ‘Finish’ in the diagram below). How many possible unique paths are there?

Example :

Input : A = 2, B = 2
Output : 2

2 possible routes : (0, 0) -> (0, 1) -> (1, 1) 
              OR  : (0, 0) -> (1, 0) -> (1, 1)

Since the robot can only move right and down, when it arrives at a point, it either arrives from left or above. If we use dp[i][j] for the number of unique paths to arrive at the point (i,j), then the state equation is dp[i][j] = dp[i][j - 1] + dp[i - 1][j]. Moreover, we have the base cases dp[0][j] = dp[i][0] = 1 for all valid i and j. Check the below figure for a better understanding.

class Solution {
  public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int i = 0; i < n; i++) dp[0][i] = 1;
    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];
  }
}

The above solution runs in O(m*n) time and costs O(m*n) space. However, you may have noticed that each time when we update dp[i][j], we only need dp[i - 1][j] (at the previous row) and dp[i][j - 1] (at the current row). So we can reduce the memory usage to just two rows (O(n)).

class Solution {
  public int uniquePaths(int m, int n) {
    int[] previousRow = new int[n];
    int[] currentRow = new int[n];
    for (int i = 0; i < n; i++) {
      previousRow[i] = 1;
      currentRow[i] = 1;
    }
    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        currentRow[j] = previousRow[j] + currentRow[j - 1];
      }
      previousRow = currentRow;
    }
    return currentRow[n - 1];
  }
}

Further inspecting the above code, previousRow[j] is just the currentRow[j] before the update. So we can further reduce the memory usage to one row.

class Solution {
  public int uniquePaths(int m, int n) {
    int[] currentRow = new int[n];
    for (int i = 0; i < n; i++) {
      currentRow[i] = 1;
    }
    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        currentRow[j] = currentRow[j] + currentRow[j - 1];
      }
    }
    return currentRow[n - 1];
  }
}

The problem can also be solved using backtracking and Memoization. This approach is more useful when the robot can move in multiple directions like left, right, top, bottom or diagonally.

class Solution {

  public int uniquePaths(int m, int n) {
    int[][] board = new int[m][n];
    board[m - 1][n - 1] = 1;
    int count = backTrack(board, m, n, 0, 0);
    return count;
  }

  private int backTrack(int[][] board, int m, int n, int i, int j) {
    if (i == m || j == n) return 0;
    if (board[i][j] != 0) return board[i][j];
    int c1 = backTrack(board, m, n, (i + 1), j);
    int c2 = backTrack(board, m, n, i, (j + 1));
    board[i][j] = (c1 + c2);
    return board[i][j];
  }
}

The backtracking solution also runs in O(m*n) times. ​

2 replies

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s