Last Updated: 7 Jan, 2021
Unique Paths
Moderate
Asked in companies
You are present at point ‘A’ which is the top-left cell of an M X N matrix, your destination is point ‘B’, which is the bottom-right cell of the same matrix. Your task is to find the total number of unique paths from point ‘A’ to point ‘B’.In other words, you will be given the dimensions of the matrix as integers ‘M’ and ‘N’, your task is to find the total number of unique paths from the cell MATRIX[0][0] to MATRIX['M' - 1]['N' - 1].
To traverse in the matrix, you can either move Right or Down at each step. For example in a given point MATRIX[i] [j], you can move to either MATRIX[i + 1][j] or MATRIX[i][j + 1].
Input Format:
The first line of input contains an integer 'T' representing the number of the test case.
The first and the only line of each test case contains two space-separated integers ‘M’ and ‘N’, denoting the number of rows and number of columns of the matrix respectively.
Output Format:
For every test case, return a single integer, which is the total number of unique paths for traveling from top-left to bottom-right cells of the matrix.
The output of each test case is printed in a separate line.
Note:
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 ≤ T ≤ 100
1 ≤ M ≤ 15
1 ≤ N ≤ 15
Where ‘M’ is the number of rows and ‘N’ is the number of columns in the matrix.
Time limit: 1 sec
Approaches
We can easily count the total number of paths by making a recursive algorithm.
The steps are as follows:
- We are given a function UNIQUEPATHS(), which takes two integers ‘M’ and ‘N’ as parameters and returns a single integer. This will be the definition of our recursive function too.
- As our base condition, we will check if our number of rows (‘M’) or a number of columns (‘N’) is equal to 1. If either one of them is equal to 1, this will mean that it is a 1-D array, and only a single path will be available. Hence we will return 1.
- If our base condition is not satisfied, we will proceed by calling our recursive function, UNIQUEPATHS() by providing it with the left and upper submatrix. Hence we will return UNIQUEPATHS('M', ‘N’ - 1) + UNIQUEPATHS('M' - 1, ‘N’).
- After all the recursive calls, the function UNIQUEPATHS() will return the final answer.
Our last approach was very simple and easy, but it’s time complexity was of exponential order. We can improve our solution by taking care of the overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again by storing them in a lookup table. This approach is known as Memoization.
The steps are as follows:
- We are given a function UNIQUEPATHS(), which takes two integers ‘M’ and ‘N’ as parameters and returns a single integer. This will be the definition of our recursive function too.
- We will initialize a 2-D lookup table ‘lookupTable’ of size ‘M’ * ‘N’ and initialize it with -1.
- We will create a helper function UNIQUEPATHSHELPER() and along with ‘M’ and ‘N’, we will also pass the 2D vector 'lookupTable'. This will be the definition of our recursive function.
- As our base condition, we will check if our number of rows (‘M’) or a number of columns (‘N’) is equal to 1. If either one of them is equal to 1, this will mean that it is a 1-D array, and only a single path will be available. Hence we will return 1.
- Now we will check if the result of the current subproblem is already stored in the ‘lookupTable’ vector or not. If the result exists, we will return it.
- Otherwise, we will call our recursive function UNIQUEPATHSHELPER() and store the returned value in ‘lookupTable’ in the variable ‘TEMP’.
- Finally, we will return ‘TEMP’ as our answer.
As we already know that we can improve our solution by taking care of the overlapping subproblems. Also, we can obtain the optimal solution of the problem by using the optimal solutions of its subproblems. Here, the concept of Dynamic Programming can be applied here and we can avoid the recomputation of the same subproblems by storing the result in a temporary 2-D array ‘DP’.
The steps are as follows:
- We are given a function UNIQUEPATHS(), which takes two integers ‘M’ and ‘N’ as parameters and returns a single integer. This will be the definition of our recursive function too.
- Create a temporary 2D array ‘DP’ of ‘M’ rows and ‘N’ columns to store the results of subproblems
- Now we apply the Dynamic Programming approach, we will first store the count of paths to reach cells in the first row and column. Then using the bottom-up recursive approach we will find the count of paths to reach other cells by using the values of subproblems.
- Finally, we will return the value of the last cell, which is ‘DP[M - 1][N - 1]' as our final answer.
The previous approach improved our solution to a large extent by avoiding the common subproblem recomputations. But the space complexity can be even further improved as the results of subproblems can also be stored in a 1-D array.
The steps are as follows:
- We are given a function UNIQUEPATHS(), which takes two integers ‘M’ and ‘N’ as parameters and returns a single integer. This will be the definition of our recursive function too.
- Create a temporary 1-D array ‘DP’ of size ‘N’, which is the number of rows of the matrix. Initialise every element of the array as 1.
- Now we apply the Dynamic Programming approach, we will first store ‘DP[0]’ = 1 as our base problem. Then using the bottom-up recursive approach we will find the count of paths to reach other cells by using the values of subproblems.
- Finally, we will return the value of the last cell, which is ‘DP[[N - 1]’ as our final answer.