Unique Paths
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

Question

Unique Paths

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

Accepted Answer

Step 1 first create a array/list variable of size same as given size of m x n grid and assign 1st ROW & COL to 1.
Step 2 Create a loop for row (starting from 1 to m) and then Create a loop for col (starting from 1 to n)
Step 3 Using 2 for loops u need to add top row value and left column value as compare to current array index. and then store the updated value to current array index.
Step 4 at the end of the loop just return last array index value.

Solution:-
dp = [[1]*n]*m
for i in range(1,m):
for j in range(1,n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]

Accepted Answer

Recursive Approach

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.

Space Complexity: OtherExplanation:

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

Time Complexity: OtherExplanation:

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

Accepted Answer

Memoization

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.

Space Complexity: O(m*n) - For 2d arraysExplanation:

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

Since the lookup table takes the space of M * N cells and thus the space complexity will be O(M * N).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(M * N), Where ‘M’ is the number of rows and ‘N’ is the number of columns of the matrix

Since the recursive approach will do the work in the order M * N. Thus the worst-case time complexity will be O(M * N).

Python (3.5)

"""

    Time Complexity  : O(M * N) 

    Space Complexity : O(M * N)

    

    Where 'M' is the number of rows and 'N' is the number of columns of the matrix.   

"""



def uniquePathsHelper(m, n, lookupTable):



    # Base condition.

    if(m == 1 or n == 1):           

        return 1

    

    # Check for solved subproblems.

    if(lookupTable[m][n] != -1):    

        return lookupTable[m][n]



    # Recursive call.

    temp = uniquePathsHelper(m - 1, n, lookupTable) + uniquePathsHelper(m, n - 1, lookupTable)

    lookupTable[m][n] = temp

    

    return temp                  



def uniquePaths(m, n):

    

    # Lookup table.

    lookupTable = [[-1 for i in range(n+1)] for j in range(m+1)]      



    # Calling helper function.

    return uniquePathsHelper(m,n,lookupTable)

C++ (g++ 5.4)

/*

    Time Complexity  : O(M * N) 

    Space Complexity : O(M * N)

    

    Where 'M' is the number of rows and 'N' is the number of columns of the matrix. 

*/



int uniquePathsHelper(int m, int n, vector> &lookupTable) 

{

    // Base condition.

	if(m == 1 || n == 1) 

	{             

		return 1;

	}



    // Check for solved subproblems.

    if(lookupTable[m][n] != -1) 

	{       

        return lookupTable[m][n];

    }



    // Recursive call.

	int temp = uniquePathsHelper(m - 1, n, lookupTable) + uniquePathsHelper(m, n - 1, lookupTable);  

    lookupTable[m][n] = temp;

    

	return temp;                     

}



int uniquePaths(int m, int n) 

{

    // Lookup table.

	vector>lookupTable(m + 1,vector(n + 1,-1));           



    // Calling helper function.

	return uniquePathsHelper(m,n,lookupTable);                             

}

Java (SE 1.8)

/*
    Time Complexity  : O(M * N) 
    Space Complexity : O(M * N)
    
    Where 'M' is the number of rows and 'N' is the number of columns of the matrix.   
*/

import java.util.Arrays;

public class Solution {
	static int uniquePathsHelper(int m, int n, int[][] lookupTable) {
		// Base condition
		if (m == 1 || n == 1) { 
			return 1;
		}

		// Check for solved subproblems.
		if (lookupTable[m][n] != -1) { 
			return lookupTable[m][n];
		}
		
		// Recursive call.
		int temp = uniquePathsHelper(m - 1, n, lookupTable) + uniquePathsHelper(m, n - 1, lookupTable); 
		lookupTable[m][n] = temp;
		return temp;
	}

	public static int uniquePaths(int m, int n) {
		// Lookup table.
		int[][] lookupTable = new int[m + 1][n + 1]; 
		for (int[] row : lookupTable) {
			Arrays.fill(row, -1);
		}

		// Calling helper function.
		return uniquePathsHelper(m, n, lookupTable); 
	}
}

Accepted Answer

Dynamic Programming

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.

Space Complexity: O(m*n) - For 2d arraysExplanation:

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

Since we are storing elements in a 2-D Array, total space taken will of the order M * N. Thus the space complexity will be O(M * N).

Time Complexity: O(m*n) - For 2d arraysExplanation:

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

Since we are running a nested loop M * N times, Thus the time complexity will be O(M * N).

Python (3.5)

"""

    Time Complexity  : O(M * N) 

    Space Complexity : O(M * N)

    

    Where 'M' is the number of rows and 'N' is the number of columns of the matrix.   

"""



def uniquePaths(m, n):



    # Reference table to store subproblems.

    dp = [[0 for i in range(n)] for j in range(m)]                  



    # Paths to reach a cell in column 1.

    for i in range(m):

        dp[i][0] = 1

    

    # Paths to reach a cell in row 1.

    for j in range(n):  

        dp[0][j] = 1

    

    # Bottom up approach.

    for i in range(1, m):  

        for j in range(1, n):  

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



    # Returning answer.

    return dp[m - 1][n - 1]

Java (SE 1.8)

/*
    Time Complexity  : O(M * N) 
    Space Complexity : O(M * N)
    
    Where 'M' is the number of rows and 'N' is the number of columns of the matrix.  
*/

public class Solution {
	public static int uniquePaths(int m, int n) {
		// Reference table to store subproblems.
		int[][] dp = new int[m][n];

		// Paths to reach a cell in column 1.
		for (int i = 0; i < m; i++) {
			dp[i][0] = 1;
		}

		// Paths to reach a cell in row 1.
		for (int j = 0; j < n; j++) {
			dp[0][j] = 1;
		}

		// Bottom up approach.
		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];
			}
		}

		// Returning answer.
		return dp[m - 1][n - 1];
	}
}

C++ (g++ 5.4)

/*

    Time Complexity  : O(M * N) 

    Space Complexity : O(M * N)

    

    Where 'M' is the number of rows and 'N' is the number of columns of the matrix.   

*/



int uniquePaths(int m,int n)

{

    // Reference table to store subproblems.

	int dp[m][n];                   



    // Paths to reach a cell in column 1.

	for (int i = 0; i < m; i++) 

    {   

        dp[i][0] = 1; 

    }



    // Paths to reach a cell in row 1.

    for (int j = 0; j < n; j++) 

    {   

        dp[0][j] = 1; 

    }       



    // Bottom up approach.

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

        }

    } 



    // Returning answer.

    return dp[m - 1][n - 1];        

}

Accepted Answer

Dynamic Programming Space optimized

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.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of columns of the matrix

Since we are storing elements in an array of size N, Thus the space complexity will be O(N).

Time Complexity: O(m*n) - For 2d arraysExplanation:

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

Since we are running a nested loop M * N times, Thus the time complexity will be O(M * N).

Java (SE 1.8)

/*
    Time Complexity  : O(M * N) 
    Space Complexity : O(N)
    
    Where 'M' is the number of rows and 'N' is the number of columns of the matrix.    
*/

public class Solution {
	public static int uniquePaths(int m, int n) {
		// Reference array to store subproblems.
		int[] dp = new int[n];
		dp[0] = 1;

		// Bottom up approach.
		for (int i = 0; i < m; i++) {
			for (int j = 1; j < n; j++) {
				dp[j] += dp[j - 1];
			}
		}
		
		// Returning answer.
		return dp[n - 1];
	}
}

Python (3.5)

"""

    Time Complexity  : O(M * N) 

    Space Complexity : O(N)

    

    Where 'M' is the number of rows and 'N' is the number of columns of the matrix.   

"""



def uniquePaths(m, n):



    # Reference array to store subproblems.

    dp = [0 for i in range(n)]                  



    dp[0] = 1



    # Bottom up approach.

    for i in range(m): 



        for j in range(1, n):

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

        

    # Returning answer.

    return dp[n - 1]

C++ (g++ 5.4)

/*

    Time Complexity  : O(M * N) 

    Space Complexity : O(N)

    

    Where 'M' is the number of rows and 'N' is the number of columns of the matrix.  

*/



int uniquePaths(int m,int n)

{

    // Reference array to store subproblems.

	int dp[n] = {1};                   



    // Bottom up approach.

    dp[0] = 1;



    for (int i = 0; i < m; i++) 

    {      

        for (int j = 1; j < n; j++) 

        { 

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

        }

    } 

    

    //Returning answer. 

    return dp[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:

Output Format:

Note:

Constraints:

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer