Problem

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

OR

There is a rat in a maze of size m x n, moving from top left corner to bottom right corner, moving only in two directions - down or right.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

Note: m and n will be such that the resulting answer fits in a 32 bit signed integer.

Examples

Example 1: 

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

Example 2:

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

Example 3:

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

Example 4:

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

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

Solution

Method 1 - DFS and Recursion

Since we know that one can only move either down or right at any point in time

  • Base case: f(N, 0) = 1, f(0, N) = 1
  • Recursion: f(N, N) = f(N, N-1) + f(N-1, N)

Code

Java
Start from 0,0
public int uniquePaths(int m, int n) {
	dfs(0, 0, m, n);
}
private int dfs(int m, int n, int x, int y) {
	if (x == m || y == n) {
		return 1;
	}
	return dfs(m, n, x, y + 1) + dfs(m, n, x + 1, y);
}
Check if end

We can also start from end destination, and shift our destination:

public int allPossiblePaths(int m, int n) {
	if (m == 0 || n == 0)
		return 1;
	return allPossiblePaths(m - 1, n) + allPossiblePaths(m, n - 1);
}

Complexity

  • ⏰ Time complexity: O(2^max(m,n))
  • 🧺 Space complexity: O(max(m, n))

Method 2 - Top Down DP with Memoization

We have a lot of repetition in Method 1, so we can use cache.

Code

Java
public int uniquePaths(int m, int n) {
	int[][] memo = new int[m][n];

	//init with -1 value
	for (int i = 0; i<m; i++) {
		Arrays.fill(memo[i], -1);
	}

	return dfs(m - 1, n - 1, memo);
}

private int dfs( int m, int n, int[][] memo) {
	//edge has only one path
	if (m == 0 || n == 0) {
		memo[m][n] = 1;
		return 1;
	}

	if (memo[m][n] != -1) {
		return memo[m][n];
	}

	memo[m][n] = dfs(m, n - 1, memo) + dfs(m - 1, n, memo);

	return memo[m][n];
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(m*n)

Method 3 - Bottom up DP

We can start filling numbers of ways we can reach to point [i,j] from [0,0]. For the first row, we can just reach in one way, from left to right. Likewise, for first column, we can reach in 1 way, i.e. top to bottom. For the 4X5 matrix:

Now, that we have the base case, we can start filling further. Now we will start filling row wise. For eg. For first row, we can either come from left or top, hence 2 ways. Likewise, we can fill remaining row. Total:

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

Code

Java
public int uniquePaths(int m, int n) {
	if (m == 0 || n == 0) {
		return 0;
	}
	if (m == 1 || n == 1) {
		return 1;
	}

	int[][] dp = new int[m][n];

	//left column
	for (int i = 0; i<m; i++) {
		dp[i][0] = 1;
	}

	//top row
	for (int j = 0; j<n; j++) {
		dp[0][j] = 1;
	}

	//fill up the dp table
	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];
}

Method 4 - Mathematics

This problem can be modelled as a math combinatorics problem.

  • We start at (0, 0) cell and end at (m-1, n-1) cell.
  • We have to make m-1 down-moves and n-1 right-moves to reach the destination cell.
  • Hence, we need to perform a total number of m+n-2 moves.
  • At each cell along the path, we can choose either the right-move or down-move and we need to find the number of unique combinations of these choices (which eventually leads to unique paths).
  • This is nothing but calculating the number of different ways to choose m-1 down-moves and n-1 right-moves from a total of m+n-2 moves.

Hence we have to calculate:

$$ \text{Number of moves} = \binom{m + n - 2}{m - 1} OR \binom{m + n - 2}{n - 1} $$

we can use Binomial Coefficient to do so. Or we can solve the relation below:

$$ \binom{m + n - 2}{m - 1} = \binom{m + n - 2}{n - 1} = \frac{(m + n - 2)!}{(m - 1)!(n-1)!} $$ $$ \implies \binom{m + n - 2}{m - 1} = \frac{(m + n - 2) * (m + n - 3) * … * (m + n - n) * (m - 1)!}{(m - 1)!(n-1)!} $$ $$ \implies = \frac{(m + n - 2) * (m + n - 3) * … * m}{(n-1)!} $$ $$ \implies = \frac{(m + n - 2) * (m + n - 3) * … * m}{(n-1) * (n - 2) … * 2 * 1} $$

We could have cancelled out the (n-1)! as well in the above evaluation, but we will do one of those based on min(m,n) to give best time complexity in the solution below.

Code

Java
public class Solution {

	public int uniquePaths(int m, int n) {
		long ans = 1;

		for (int i = m + n - 2, j = 1; i >= Math.max(m, n); i--, j++) {
			ans = (ans * i) / j;
		}

		return (int) ans;
	}
}

Complexity

  • ⏰ Time complexity: O(max(m, n))
  • 🧺 Space complexity: O(1)