Home » Interview coding problems/challenges

# Number of Unique Paths

**Number of Unique Paths**: This is a standard dynamic problem which can be featured in any interview coding.

Submitted by Radib Kar, on February 16, 2020

**Description:**

In this article, we are going to see a standard dynamic problem which can be featured in any interview coding.

**Problem statement:**

Given a **M X N matrix** with initial position at top-left cell, **find the number of possible unique paths to reach the bottom right cell of the matrix from the initial position**. Possible moves can be either **down** or **right** at any point in time.

Input: The first line contains an integer T, depicting total number of test cases. Then following T lines contains two integers m and n depicting the size of the grid. Output: Print the number of unique paths to reach bottom-right cell from the top-left cell.

**Example with explanation:**

Input: 2 3 3 3 4 Output: 6 10

So, for the first test case, **M=3, n=3**

Grid is like,

1. (0,0)->(0,1)->(0,2)->(1,2)->(2,2)

2. (0,0)->(0,1)->(1,1)->(1,2)->(2,2)

3. (0,0)->(0,1)->(1,1)->(2,1)->(2,2)

4. (0,0)->(1,0)->(2,0)->(2,1)->(2,2)

5. (0,0)->(1,0)->(1,1)->(1,2)->(2,2)

6. (0,0)->(1,0)->(1,1)->(2,1)->(2,2)

**This are the possible unique paths and hence count is 6.**

Given a matrix with an initial position at the top-left cell, find the number of possible unique paths to reach the bottom-right cell of the matrix from the initial position. Possible moves can be either or at any point in time.

**Recursion Algorithm:**

Of course, we can generate a recursion algorithm. Since the only possible moves are down and right from any point, we can write a recursive relation, f(m,n) = f(m-1,n) + f(m,n-1) Where f(m,n) = number of unique path for grid size m,n f(m-1,n) = number of unique path for grid size [(m-1),n] a down move from the end point of this will result in f(m,n) f(m,n-1) = number of unique path for grid size [m,(n-1)] a right move from the end point of this will result in f(m,n) Hence, f(m,n) is summation of f(m-1,n) and f(m,n-1)

So, the algorithm can be:

Function Uniquepaths(m,n): 1) If m==0 & n==0 return 0 2) If m == 0 Then return 1 3) If n==0 Then return 1 4) Return Uniquepaths(m-1,n)+Uniquepaths(m,n-1)

But this would generate many overlapping subproblems, which will be computed again and again increasing the time complexity. Hence, we can convert the recursion to dynamic Programming.

**Dynamic Programming approach:**

1) Create a 2D array DP with size m, n 2) Initialize DP[0][0] =0 which is similar to step 1 in our previous function. 3) for i=1 to n-1 DP[0][i]=1 end for This is similar to step2 in our previous function 4) for i=1 to m-1 DP[i][0]=1 end for This is similar to step3 in our previous function 5) Compute the whole DP table for i=1 to m-1 for j=1 to n-1 DP[i][j]=DP[i-1][j]+DP[i][j-1] end for end for This is similar to step 4 in our previous recursive function 6) Return DP[m-1][n-1] which is the result.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int uniqueRoute(int m,int n){ int DP[m][n]; memset(DP,0,sizeof(DP)); //base cases DP[0][0]=0; for(int i=1;i<m;i++) DP[i][0]=1; for(int i=1;i<n;i++) DP[0][i]=1; //compute dp table 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]; } int main() { int t,n,m; cout<<"Enter number of testcases\n"; cin>>t; for(int i=0;i<t;i++){ cout<<"Enter grid size, m & n\n"; cin>>m>>n; cout<<"Number of unique paths from topleft to bottom right: "<<uniqueRoute(m,n)<<endl; } return 0; }

**Output**

Enter number of testcases 2 Enter grid size, m & n 3 3 Number of unique paths from topleft to bottom right: 6 Enter grid size, m & n 3 4 Number of unique paths from topleft to bottom right: 10

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.