Problem:
Given a 2 dimensional matrix size m * n , find the number of unique ways to reach the bottom right of the matrix from the top left of the matrix (first cell) if you can move only right or down a step at a time .
That is from input[0][0] to input[m-1][n-1]
For example , for the input :
m = 3 , n = 2
The output is 3:
- Right -> Down -> Down
- Down -> Down -> Right
- Down -> Right -> Down
Try out the solution here:
https://leetcode.com/problems/unique-paths/
Solution:
Hint:
You either move along the column or along the row incrementally. So ,
Number of ways to reach any position in the matrix = Number of ways to reach the previous row current column cell + Number of ways to reach the current row previous column cell
ie) Ways[i][j] = Ways [i-1][j] + Ways[i][j-1]
Where i represents the current row and j represents the current column.
We can solve the above problem recursively by setting the base conditions:
- If row or column value is negative , return 0
- If row or column value is 0 , return 1. It means there is only one row or one column. We return 1 because if there is only one row or column , then you can move only once in one direction to reach the destination.
Once the base conditions are set , recursively compute the number of ways to reach previous row and current column position . Also recursively compute the number of ways to reach previous column and current row position. Add them both and return.
Here is the code:
Recursion Code:
class Solution {
public int uniquePaths(int m, int n) {
return recursion(m-1,n-1);
}
public int recursion(int right,int down){
if(right < 0 || down < 0){
return 0;
}
if( right ==0 || down ==0) return 1;
return recursion(right - 1, down)+ recursion(right , down -1);
}
}
The time complexity is exponential in the above case because of the recursive calls. We can avoid repeated recursive calls by storing the result of the recursive calls in an array . This technique is known as Memoization. So you return the result from the array if already present and make the recursive call only if not present.
Memoization Code:
Code is very similar to the above except for storing result of the sub problems in an array and returning results from it.
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
return recursion(m-1,n-1,dp);
}
public int recursion(int right,int down,int[][] dp){
if(dp[right][down] !=0){
return dp[right][down];
}
if(right < 0 || down < 0){
return 0;
}
if( right ==0 || down ==0) return 1;
int result = recursion(right - 1, down,dp)+ recursion(right , down -1,dp);
dp[right][down] = result;
return result;
}
}
You can further avoid the recursion calls altogether using bottom up dynamic programming this way:
Bottom Up Dynamic Programming:
ALGORITHM:
STEP 1: Initialize an output array to store the results of number of unique paths at each index of the matrix
STEP 2: For the first row and first column values initialize the output as 1 as there is only one way to reach the end of the matrix if there is only one row or one column.
STEP 3: For all other positions , calculate the output using formula:
Number of unique paths to a position in the matrix = Number of unique ways till the previous row , current column + Number of unique ways till the previous column, current row
STEP 4: Return the value of the last element which represents the bottom right element.
Code:
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 j=0;j<n;j++){
dp[0][j] = 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];
}
}
Time complexity is O(m * n ) where m and n are the dimensions of the matrix and space complexity is also O( m * n) as we use a two dimensional array to store the results .
We can do one more optimization here.
If you notice the code :
dp[i][j] = dp[i-1][j]+dp[i][j-1];
The result above represents the sum of the value in the previous row for the current column and the value in the current row previous column.
It could be replaced by a one dimensional array and using the below code:
dp[j] = dp[j]+dp[j-1];
In the above sum , the first operand dp[j] represents the value of the current column in the previous row and the second operand dp[j-1] represents the value of the previous column in the current row. Adding both gives the new dp[j] which represents the value of the current row and current column.
Since both the sums return the same value, so we can use the later and minimize the space used.
Here is the refactored code:
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
for(int j=0;j<n;j++){
dp[j] = 1;
}
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 complexity remains the same O(m * n) whereas space complexity is reduced to O(n)
Let’s understand this visually using the below example :
Let’s take the 3 * 2 matrix again.
Let’s first initialize all the values to 1:
Notice that dp[0] represents the first column value for all the rows.
dp[1] represents the second column values for all the rows.
Now let’s use the formula
dp[j] = dp[j]+ dp[j-1]
Lets use it for j = 1 and i = 1 (second row and second column)
We are now going to calculate dp[1] for the second row.
As we have already learned the formula
Number of unique paths at a position = Number of unique paths at the previous row current column + Number of unique paths at the current previous column
dp[1] = Number of unique paths at column 1 , row 0 + Number of unique paths at column 0 , row 1. From the above diagram you can easily add both and find the solution as 2 (1 + 1)
Let us use the formula to find the same:
Number of unique paths at column 1 row 0 dp[1] is already initialized to 1
Number of unique paths at column 0 row 1 dp[0] is also already initialized to 1.
So ,
dp[1] (for current row) = dp [1] (for previous row) + dp[0] = 1 + 1 = 2
Now lets take i = 2 , j = 1
Again use the formula
dp[1] (for row 2) = dp[1] (for row 1 already calculated in the previous step) + dp[0] (for row 2)
dp[1] = 2 + 1 = 3
Return the last value 3.
That’s it!
Leave a Reply