Unique Paths

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
288 upvotes
Asked in companies
AdobeZomatoCisco

Problem statement

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].

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 2
1 1
Sample Output 1:
2
1
Explanation of Sample Output 1:
In test case 1, we are given a 2 x 2 matrix, to move from matrix[0][0] to matrix[1][1] we have the following possible paths.

Path 1 = (0, 0) -> (0, 1) -> (1, 1)
Path 2 = (0, 0) -> (1, 0) -> (1, 1)

Hence a total of 2 paths are available, so the output is 2.

In test case 2, we are given a 1 x 1 matrix, hence we just have a single cell which is both the starting and ending point. Hence the output is 1.
Sample Input 2:
2
3 2
1 6
Sample Output 2:
3
1
Explanation of Sample Output 2:
In test case 1, we are given a 3 x 2 matrix, to move from matrix[0][0] to matrix[2][1] we have the following possible paths.

Path 1 = (0, 0) -> (0, 1) -> (1, 1) -> (2, 1)
Path 2 = (0, 0) -> (1, 0) -> (2, 0) -> (2, 1)
Path 3 =  (0, 0) -> (1, 0) -> (1, 1) -> (2, 1)

Hence a total of 3 paths are available, so the output is 3.

In test case 2, we are given a 1 x 6 matrix, hence we just have a single row to traverse and thus total path will be 1.
Hint

Can you think of a recursive algorithm to count all the paths?

Approaches (4)
Recursive Approach

We can easily count the total number of paths by making a recursive algorithm.

 

The steps are as follows:

 

  1. 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.
  2. 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.
  3. 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’).
  4. After all the recursive calls, the function UNIQUEPATHS() will return the final answer.
Time Complexity

O(2 ^ (M + N)), Where ‘M’ is the number of rows and ‘N’ is the number of columns of the matrix.

 

Since for every recursive call, two more recursive calls are taking place. Thus the worst-case time complexity will be O(2 ^ (M + N)).

Space Complexity

O(max(M, N)), where M is the number of rows and N is the number of columns of the matrix

 

Since due to the recursion stack space, the space complexity will be O(max(M, N)).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Unique Paths
Full screen
Console