Unique Paths Editorial

Practice Problem Link: Unique Paths

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

A rat is located at the top-left cell of an m * n matrix. The rat wants to get to the cheese which is at the bottom-right cell of the matrix. The rat can move only in one of the two directions - down and right. How many unique paths can the rat take to reach the destination?

Naive Approach

The naive approach is to use a brute recursion to calculate all the possible ways of reaching the destination cell, using the valid available moves.

Analysis

• Time Complexity: Exponential
• Space Complexity: O(m * n)

Implementation

C++

const int MOD = (int)1e9 + 7;
int uniquePathsUtil(int m, int n) {
	if(m == 1 || n == 1) {
		return 1;
	}
	return (uniquePathsUtil(m - 1, n) + uniquePathsUtil(m, n - 1)) % MOD;
}
int uniquePaths(int m, int n) {
	return uniquePathsUtil(m, n);
}

Java

class Solution {
	int MOD = (int)1e9 + 7;
	int uniquePathsUtil(int m, int n) {
	if(m == 1 || n == 1) {
		return 1;
	}
	return (uniquePathsUtil(m - 1, n) + uniquePathsUtil(m, n - 1)) % MOD;
	}
	int uniquePaths(int m, int n) {
		return uniquePathsUtil(m, n);
	}
}

Optimized Approach

We can observe in this problem that multiple function calls are called again and again. So, we can memoize these function calls with a Dynamic Programming Approach, to reduce the complexity to polynomial time.

Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)

Implementation

C++

const int MOD = (int)1e9 + 7;
vector<vector<int>> dp;
int uniquePathsUtil(int m, int n) {
	if(m == 1 || n == 1) {
		return 1;
	}
	if(dp[m][n] != -1) {
		return dp[m][n];
	}
	return dp[m][n] = (uniquePathsUtil(m - 1, n) + uniquePathsUtil(m, n - 1)) % MOD;
}
int uniquePaths(int m, int n) {
	vector<vector<int>> temp(m + 1, vector<int> (n + 1, -1));
	dp = temp;
	return uniquePathsUtil(m, n);
}

Java

class Solution {
	int MOD = (int)1e9 + 7;
	int[][] dp;
	int uniquePathsUtil(int m, int n) {
	if(m == 1 || n == 1) {
		return 1;
	}
	if(dp[m][n] != -1) {
		return dp[m][n];
	}
	return dp[m][n] = (uniquePathsUtil(m - 1, n) + uniquePathsUtil(m, n - 1)) % MOD;
	}
	int uniquePaths(int m, int n) {
		dp = new int[m + 1][n + 1];
		for(int i = 0; i <= m; i++) {
			Arrays.fill(dp[i], -1);
		}
		return uniquePathsUtil(m, n);
	}
}

Implementation (Bottom - Up)

C++

const int MOD = (int)1e9 + 7;
int uniquePaths(int m, int n) {
	int dp[m][n];
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			if(i == 0 || j == 0) {
				dp[i][j] = 1;
			}
			else {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
			dp[i][j] %= MOD;
		}
	}
	return dp[m - 1][n - 1];
}

Java

class Solution {
	int MOD = (int)1e9 + 7;
	int uniquePaths(int m, int n) {
		int[][] dp = new int[m][n];
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < n; j++) {
				if(i == 0 || j == 0) {
					dp[i][j] = 1;
				}
				else {
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				}
				dp[i][j] %= MOD;
			}
		}
		return dp[m - 1][n - 1];
	}
}

Optimal Approach

We can solve this problem optimally in linear time using some basic combinatorics. Notice that to reach the target we need to make a total of n - 1 right moves and m - 1 down moves, in some order. To make these moves, we can choose a total of n - 1 right moves out of a total of n + m - 2 moves, which gives us our required formula (n + m - 2) C (n - 1).

Analysis

• Time Complexity: O(n + m)
• Space Complexity: O(n + m)

Implementation

C++

int MOD = (int)1e9 + 7;
vector<int> fact, invfact;
int power(int x, int y, int p)  {
    long long res = 1;
    x = x % p;
    if (x == 0) {
		return 0;
	}
    while (y > 0) {
        if (y & 1) { 
            res = (res * 1LL * x) % p;
		}
        y = y >> 1LL;  
        x = (x * 1LL * x) % p;  
    }  
    return res;  
}  
void precomputeFactorials(int N) {
	fact.resize(N + 1);
	invfact.resize(N + 1);
	fact[0] = 1;
	invfact[0] = 1;
	for(int i = 1; i <= N; i++) {
		fact[i] = (fact[i - 1] * 1LL * i) % MOD;
		invfact[i] = power(fact[i], MOD - 2, MOD);
	}
}
int NCR(int n, int r) {
	if(n < r || n < 0 || r < 0) {
		return 0;
	}
	int ans = (invfact[r] * 1LL * invfact[n - r]) % MOD;
	ans = (ans * 1LL * fact[n]) % MOD;
	return ans;
}
int uniquePaths(int m, int n) {
	precomputeFactorials(n + m);
	return NCR(n + m - 2, n - 1);
}

Java

class Solution {
	int MOD = (int)1e9 + 7;
	long power(long x, long y, long p)  {
		long res = 1;
		x = x % p;
		if (x == 0) {
			return 0;
		}
		while (y > 0) {
			if (y % 2 != 0) { 
				res = (res * x) % p;
			}
			y = y >> 1;  
			x = (x * x) % p;  
		}  
		return res;  
	}  
	int uniquePaths(int m, int n) {
		long top = 1, bottom1 = 1, bottom2 = 1;
		for(int i = 1; i <= m + n - 2; i++) {
			top = (top * i) % MOD;
		}
		for(int i = 1; i <= n - 1; i++) {
			bottom1 = (bottom1 * i) % MOD;
		}
		for(int i = 1; i <= m - 1; i++) {
			bottom2 = (bottom2 * i) % MOD;
		}
		bottom1 = power(bottom1, MOD - 2, MOD);
		bottom2 = power(bottom2, MOD - 2, MOD);
		long result = top;
		result = (result * bottom1) % MOD;
		result = (result * bottom2) % MOD;
		return (int)result;
	}
}