A m x n 2D grid is given and you are standing at the topmost and leftmost cell in the grid. i.e. the cell located at (1,1). Find the number of unique paths that can be taken to reach a cell located at (m,n) from the cell located at (1,1) given that you can move downwards or rightwards only.
Input 1: m = 3, n = 3 Output: 6 Input 2: m = 3, n = 2 Output: 3
Table of Contents
Types of solution For Unique Paths
- Recursive
- Dynamic Programming
- Top-down Approach
- Bottom-up Approach
- Bottom-up space-optimized Approach
- Combinatorics
Recursive
Approach for Unique Paths
For any cell (m,n) i.e. cell located at coordinates (m,n), the number of ways to reach it from the cell (1,1) is the sum of {number of unique paths to reach cell (m-1,n), the number of unique paths to reach cell (m,n-1)}, given that you can move towards the right and down only.
Therefore, Problem(m,n) = Problem(m-1,n) + Problem(m,n-1). In this way recursively reducing larger problems to smaller subproblems and defining base cases we can find the solution for a larger problem.
Algorithm
- Define the base case, for a single row/column.
- Define the recursive solution i.e. uniquePath(m,n) = uniquePath(m-1,n) + uniquePath(m,n-1).
- return the solution.
Implementation
C++ Program For Unique Paths
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* function that returns number of paths
to move from start-cell at (1,1) to cell at(m,n)
in a 2D grid */
int uniquePath(int m,int n)
{
/* if there exists only 1 row or 1 column in the grid
number of paths/ways to reach cell(m,n) is unique */
if(m == 1 || n == 1)
return 1;
/* since, only downwards and rightwards movements are allowed
number of paths to reach cell at (m,n) is sum of number of paths
to reach cell at (m-1,n) and cell at (m,n-1) */
return uniquePath(m-1,n) + uniquePath(m,n-1);
}
/* main function to implement above function */
int main()
{
/* grid of 3 x 3 */
int m = 3,n = 3;
cout<<"Number of unique path for grid of "<<m<<" x "<<n<<" = "<<uniquePath(m,n);
return 0;
}6
Java Program For Unique Paths
import java.util.*;
import java.io.*;
class tutorialCup
{
/* function that returns number of paths
to move from start-cell at (1,1) to cell at(m,n)
in a 2D grid */
static int uniquePath(int m,int n)
{
/* if there exists only 1 row or 1 column in the grid
number of paths/ways to reach cell(m,n) is unique */
if(m == 1 || n == 1)
return 1;
/* since, only downwards and rightwards movements are allowed
number of paths to reach cell at (m,n) is sum of number of paths
to reach cell at (m-1,n) and cell at (m,n-1) */
return uniquePath(m-1,n) + uniquePath(m,n-1);
}
/* main function to implement above function */
public static void main (String[] args)
{
/* grid of 3 x 3 */
int m = 3,n = 3;
System.out.println("Number of unique path for grid of "+m+" x "+n+" = "+uniquePath(m,n));
}
}6
Complexity Analysis
- Time Complexity : T(n) = O(2max(m,n)), exponential time.
- Space Complexity : A(n) = O(1) or O(2max(m,n)), considering recursion stack space.
Dynamic Programming
The idea of dynamic programming is to simply store/save the results of various subproblems calculated during repeated recursive calls so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.
Consider the following recursion tree diagram of a unique path(3,3) :
We observe that solutions for subproblems uniquePath(2,2), uniquePath(2,1) and uniquePath(1,2) are evaluated (as 2,1,1 respectively) repeatedly. this repeated calculation of solution of the same subproblems occurs more often in case of larger strings. The extra effort in calculating the same subproblem repeatedly costs time overhead and increases the complexity of the algorithm.
The objective of Dynamic Programming Solution is to store/save solutions of subproblems and produce them (instead of calculating again) whenever the algorithm requires that particular solution. This method hugely reduces the time complexity.
It is observed that time complexity is reduced from exponential order to polynomial order which is less computationally intensive.
Top-down Approach (Memoization)
Approach for Unique Paths
We save/store the solution of each subproblem. This is done using a Map data structure where the subproblem is the key and its numerical solution is the value. In simpler words, we map the subproblem (key) to the solution (value). The subproblem is converted to a string and mapped to a numerical solution. we create a hashmap ‘memo’, this memo has subproblems (string data type) as key and solution(Integer data type) as value.
When we call uniquePath(x,y) for a subproblem (x,y), we check whether the solution to that subproblem has been stored in the Map or not. If it is already stored, we directly use that value or else calculate the value. In the end, we simply return the value already stored or calculated (as the case may be).
The following table shows subproblems, their corresponding keys, and values :
Algorithm
- Create a hashmap memo to store the mapping of subproblems to their respective solutions.
- convert subproblem (m,n) to string and check whether it has been already calculated and stored in a memo or not.
- If the solution for (m,n) has been already calculated then simply return the mapped integer solution of subproblem(m,n).
- Else calculate the solution for subproblem in the following way :
- Define the base case, for a single row/column.
- Define the recursive solution i.e. uniquePath(m,n) = uniquePath(m-1,n) + uniquePath(m,n-1).
- Map the subproblem to the solution obtained above and return the solution.
Implementation
C++ Program For Unique Paths
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* function that returns number of paths
to move from start-cell at (1,1) to cell at(m,n)
in a 2D grid */
int uniquePath(int m,int n,unordered_map<string,int> &memo)
{
/* creating a subproblem (m,n) */
string key = to_string(m) + "|" + to_string(n);
/* if subproblem (m,n) has not been solved
then solve it */
if(memo.find(key) == memo.end())
{
/* if there exists only 1 row or 1 column in the grid
number of paths/ways to reach cell(m,n) is unique */
if(m == 1 || n == 1)
memo[key] = 1;
else
/* since, only downwards and rightwards movements are allowed
number of paths to reach cell at (m,n) is sum of number of paths
to reach cell at (m-1,n) and cell at (m,n-1) */
memo[key] = uniquePath(m-1,n,memo) + uniquePath(m,n-1,memo);
}
/* return the solution for subproblem mapped in memo */
return memo[key];
}
/* main function to implement above function */
int main()
{
/* grid of 3 x 3 */
int m = 3,n = 3;
unordered_map<string,int> memo;
cout<<"Number of unique path for grid of "<<m<<" x "<<n<<" = "<<uniquePath(m,n,memo);
return 0;
}6
Java Program For Unique Paths
import java.util.*;
import java.io.*;
class tutorialCup
{
/* function that returns number of paths
to move from start-cell at (1,1) to cell at(m,n)
in a 2D grid */
static int uniquePath(int m,int n,HashMap <String,Integer> memo)
{
/* creating a subproblem (m,n) */
String key = m + "|" + n;
/* if subproblem (m,n) has not been solved
then solve it */
if(!memo.containsKey(key))
{
/* if there exists only 1 row or 1 column in the grid
number of paths/ways to reach cell(m,n) is unique */
if(m == 1 || n == 1)
memo.put(key,1);
else
/* since, only downwards and rightwards movements are allowed
number of paths to reach cell at (m,n) is sum of number of paths
to reach cell at (m-1,n) and cell at (m,n-1) */
memo.put(key,uniquePath(m-1,n,memo) + uniquePath(m,n-1,memo));
}
/* return the solution for subproblem mapped in memo */
return memo.get(key);
}
/* main function to implement above function */
public static void main (String[] args)
{
/* grid of 3 x 3 */
int m = 3,n = 3;
HashMap <String,Integer> memo = new HashMap<>();
System.out.println("Number of unique path for grid of "+m+" x "+n+" = "+uniquePath(m,n,memo));
}
}6
Complexity Analysis
- Time Complexity : T(n) = O(mn), polynomial time.
- Space Complexity : A(n) = O(mn), considering space for mapping.
Bottom-up Approach (Tabulation)
Approach for Unique Paths
The objective of this solution is to again store the numerical solution of each of the subproblems, but using a different data structure. In this case, we utilize a table (2D array or matrix) to store solutions to the subproblems. The indices of the table are subproblems and value at that indices is the numerical solution for that particular subproblem.
Table obtained for uniquePath(3,3) is
Algorithm
- create a 2D matrix table of dimensions m x n.
- Define base cases: assign the first row and first column of the matrix as 1.
- Traverse each cell of iteratively and apply the recurrence relation: table[i][j] = table[i-1][j] + table[i][j-1].
- return the answered stored in table[m-1][n-1].
Implementation
C++ Program For Unique Paths
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* function that returns number of paths
to move from start-cell at (1,1) to cell at(m,n)
in a 2D grid */
int uniquePath(int m,int n)
{
/* create a 2D table to store results of subproblems (Tabulation) */
int table[m][n];
/* number of paths to reach any cell in first column is 1 */
for (int i = 0; i < m; i++)
table[i][0] = 1;
/* number of paths to reach any cell in first row is 1 */
for (int j = 0; j < n; j++)
table[0][j] = 1;
/* calculate number of paths to reach other cells in the grid
in bottom up manner */
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
/* since, only downwards and rightwards movements are allowed
number of paths to reach cell at (m,n) is sum of number of paths
to reach cell at (m-1,n) and cell at (m,n-1) */
table[i][j] = table[i - 1][j] + table[i][j - 1];
}
return table[m - 1][n - 1];
}
/* main function to implement above function */
int main()
{
/* grid of 3 x 3 */
int m = 3,n = 3;
cout<<"Number of unique path for grid of "<<m<<" x "<<n<<" = "<<uniquePath(m,n);
return 0;
}6
Java Program For Unique Paths
import java.util.*;
import java.io.*;
class tutorialCup
{
/* function that returns number of paths
to move from start-cell at (1,1) to cell at(m,n)
in a 2D grid */
static int uniquePath(int m,int n)
{
/* create a 2D table to store results of subproblems (Tabulation) */
int [][] table = new int[m][n];
/* number of paths to reach any cell in first column is 1 */
for (int i = 0; i < m; i++)
table[i][0] = 1;
/* number of paths to reach any cell in first row is 1 */
for (int j = 0; j < n; j++)
table[0][j] = 1;
/* calculate number of paths to reach other cells in the grid
in bottom up manner */
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
/* since, only downwards and rightwards movements are allowed
number of paths to reach cell at (m,n) is sum of number of paths
to reach cell at (m-1,n) and cell at (m,n-1) */
table[i][j] = table[i - 1][j] + table[i][j - 1];
}
return table[m - 1][n - 1];
}
/* main function to implement above function */
public static void main (String[] args)
{
/* grid of 3 x 3 */
int m = 3,n = 3;
System.out.println("Number of unique path for grid of "+m+" x "+n+" = "+uniquePath(m,n));
}
}6
Complexity Analysis
- Time Complexity : T(n) = O(mn), polynomial time.
- Space Complexity : A(n) = O(mn), space used for table.
Space optimized bottom-up Approach
Approach for Unique Paths
we observe in the above tabulation solution that for each cell (i,j) of table encountered during traversal we require only the cell above (i-1,j) and cell towards left (i,j-1). We reduce the space by simply creating a 1D table(array) of dimension m. After every iteration of the outer loop (with loop variable i), the table stores the values for the ith row of the table[i][j] (as defined in the previous section). table[j] stores the number of unique paths to reach cell (i,j) from cell(1,1). Therefore ,we obtain a recurrence relation as,
for every (i,j) : table[j](modified value) = table[j] (already stored value of the cell above) + table[j-1](already stored value for the cell to the left).
Algorithm
- create a linear array table of dimension m.
- Traverse each cell of (m,n) grid using nested loops, with outer loop variable as i and inner loop variable as j.
- inside inner loop, define the recurrence relation as: table[j] = table[j] + table[j-1].
- After traversal is over, return the last value stored in the table.
Implementation
C++ Program For Unique Paths
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* function that returns number of paths
to move from start-cell at (1,1) to cell at(m,n)
in a 2D grid */
int uniquePath(int m,int n)
{
int table[m];
/* base case */
for (int i = 0; i < m; i++)
table[i] = 1;
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
/* recurrence relation
table[j] in RHS is cell value stored above the current cell
table[j-1] in RHS is cell value stored to left of the current cell
table[j] in LHS is value of number of unique paths to reach cell (i,j)
*/
table[j] = table[j] + table[j-1];
return table[m-1];
}
/* main function to implement above function */
int main()
{
/* grid of 3 x 3 */
int m = 3,n = 3;
cout<<"Number of unique path for grid of "<<m<<" x "<<n<<" = "<<uniquePath(m,n);
return 0;
}6
Java Program For Unique Paths
import java.util.*;
import java.io.*;
class tutorialCup
{
/* function that returns number of paths
to move from start-cell at (1,1) to cell at(m,n)
in a 2D grid */
static int uniquePath(int m,int n)
{
int [] table = new int[m];
/* base case */
for (int i = 0; i < m; i++)
table[i] = 1;
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
/* recurrence relation
table[j] in RHS is cell value stored above the current cell
table[j-1] in RHS is cell value stored to left of the current cell
table[j] in LHS is value of number of unique paths to reach cell (i,j)
*/
table[j] = table[j] + table[j-1];
return table[m-1];
}
/* main function to implement above function */
public static void main (String[] args)
{
/* grid of 3 x 3 */
int m = 3,n = 3;
System.out.println("Number of unique path for grid of "+m+" x "+n+" = "+uniquePath(m,n));
}
}6
Complexity Analysis
- Time Complexity : T(n) = O(mn), exponential time.
- Space Complexity : A(n) = O(n), space used for the table.
Combinatorics
Approach for Unique Paths
We use combinatorics formulae that calculate the number of unique paths to reach destination cells starting from the cell(1,1). The formulae of the number of unique paths to reach cell(m,n) starting from the cell(1,1) is maxCmin. where
maxCmin = (max!/((min!) x (max-min)!))
Implementation
C++ Program For Unique Paths
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* function that returns number of paths
to move from start-cell at (1,1) to cell at(m,n)
in a 2D grid */
/* number of ways to reach cell at (m,n)
starting from cell at (1,1) is nCr */
int nCr(int m,int n)
{
int val = 1;
for (int i = n; i < (m + n - 1); i++)
{
val *= i;
val /= (i - n + 1);
}
return val;
}
/* main function to implement above function */
int main()
{
/* grid of 3 x 3 */
int m = 3,n = 3;
cout<<"Number of unique path for grid of "<<m<<" x "<<n<<" = "<<nCr(m,n);
return 0;
}6
Java Program For Unique Paths
import java.util.*;
import java.io.*;
class tutorialCup
{
/* function that returns number of paths
to move from start-cell at (1,1) to cell at(m,n)
in a 2D grid */
/* number of ways to reach cell at (m,n)
starting from cell at (1,1) is nCr */
static int nCr(int m,int n)
{
int val = 1;
for (int i = n; i < (m + n - 1); i++)
{
val *= i;
val /= (i - n + 1);
}
return val;
}
/* main function to implement above function */
public static void main (String[] args)
{
/* grid of 3 x 3 */
int m = 3,n = 3;
System.out.println("Number of unique path for grid of "+m+" x "+n+" = "+nCr(m,n));
}
}6
Complexity Analysis
- Time Complexity : T(n) = O(m), linear time.
- Space Complexity : A(n) = O(1).